Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Also Fortsetzung des Themas reguläre Ausdrücke.

Wir hatten letztes Mal eben zwei Dinge behauptet, die wir nicht bewiesen hatten.

Das eine war als angeblich leichte Anwendung des Satzes von Klinie,

dass ich reguläre Ausdrücke komplementieren und verunden kann.

Was also bedeutet, dass ich also praktisch reguläre Ausdrücke schreiben kann,

sodass ich, was weiß ich, alle Dateinamen suchen kann,

die ein bestimmtes Pattern matchen und ein zweites auch und ein drittes nicht zum Beispiel.

Das könnte man tun.

Hat sich jemand meiner Herausforderungen gestellt und sich mal überlegt, wie man das machen könnte

unter Anwendung des Satzes von Klinie?

Alle offenbar.

Ja, das eine ist besonders einfach. Also was sagt uns denn der Satz von Klinie?

Der Satz von Klinie sagt uns, wir können hin und her springen zwischen regulären Ausdrücken

und deterministischen Automaten.

Deterministischen, endlichen Automaten.

Wie komplementiere ich einen deterministischen, endlichen Automaten?

Also wie gegeben ein Automat? Wie baue ich einen, der genau die Wörter akzeptiert,

der der Gegebenen nicht akzeptiert?

Man muss den Automaten natürlich umbauen, nicht klar. Also irgendwas ändern am Automaten.

Ich würde sagen, man dreht einfach die Akzeptanzbedingungen oder den Akzeptanzstatus der Zustände um.

Das ist also hier Behauptung A.

Das läuft also hier jetzt alles unter Anwendung des Satzes von Klinie.

Erstens,

ich sage das mal, etwas solide reguläre Ausdrücke kann man komplementieren.

Und um das zu zeigen, wie gesagt, verwenden wir den Satz von Klinie.

Der sagt, wir können durch reguläre Ausdrücke und durch deterministische, endliche Automaten

die dieselben Sprachen beschreiben.

Das heißt, es reicht nach Klinie, entsprechendes zu zeigen für deterministische, endliche Automaten.

Also zeigen, wie ich einen DFA komplementiere.

Also ich nehme an, ich hätte einen deterministischen, endlichen Automaten gegeben.

So ein 5-Tupel unbequemerweise.

Und ich definiere dann einen Automaten aq, den Komplementautomaten.

Der sieht fast genauso aus, hat also die gleichen Zustände.

Natürlich das gleiche Alphabet, sonst könnte er nicht das Komplement akzeptieren.

Also um überhaupt zu sagen, dass das Komplement ist, muss man das Alphabet festhalten.

Er hat dann dieselbe Zustandsübergangsfunktion und denselben Initialzustand.

Nur er hat andere akzeptierende Zustände, nämlich die gerade, die vorher nicht akzeptierend waren.

Und dann leistet dieser Automat genau das, was wir wollen, nämlich die von ihm akzeptierte Sprache

ist gerade das Komplement der von a akzeptierten Sprache.

Also sigma Stern minus a.

Man müsste jetzt natürlich drängend um hingehen und das beweisen, aber es ist eben eigentlich,

wenn man die Konstruktion mal hingeschrieben hat, sonnenklar, wenn ich ein Wort eingebe, was passiert.

Nun ein Wort bestimmt mir eindeutig einen Pfad durch den Automaten, der endet bei irgendeinem Zustand.

Und ich akzeptiere, wenn dieser Zustand akzeptierend ist, also hier in aq, also genau dann, wenn er vorher nicht akzeptierend ist,

also genau dann, wenn ich das Wort vorher abgelehnt habe.

Das ist also wirklich sonnenklar, wenn man das so hingeschrieben hat.

Was wäre denn, wenn a jetzt ein nicht deterministischer Automat wäre?

Würde das auch so klappen?

Ja?