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

Ja, herzlich willkommen. Wir sind weiter bei unserem Abschlusskapitel über endliche Automaten,

ein Thema, was Sie im BFS dieses Semesters schon gesehen haben. Ich schicke nochmal eine

so moralisierende Erklärung vorweg, auch und vor allem eher an die Kamera bzw. an die Leute,

die sich das zu Hause angucken. Was jetzt in der letzten Woche kommt, ist noch klausurrelevanter

Stoff, auch wenn wir ihn leider in den abzugebenden Übungen nicht mehr abhandeln können, weil wir

nicht gut, also irgendwann muss man halt aufhören, die Übungen einzusammeln, weil die Leute dann ja

nicht mehr da sind. Wir können sie ja nicht mehr zurückgeben. Also es gibt diese Woche noch

Präsenzübung zu dem Stoff, den ich jetzt anbringe und ich wiederhole nochmal, er ist klausurrelevant.

Das heißt also insbesondere, also nicht nur nehme man das ernst, was ich jetzt an die Tafel

schreibe, sondern es lohnt sich auch eben wie gesagt einfach nochmal in die Übung zu gehen.

Ja, auf der positiven Seite ist es alles keine Rocket Science.

Ja, wir hatten die letzte Sitzung geschlossen mit einem kurzen Recap von deterministischen

und nicht deterministischen Automaten. Wir wollen heute zwei Dinge schaffen. Erstens wollen wir uns

ansehen, reguläre Ausdrücke und die Vervollständigung des sogenannten Cleaniesatzes,

nämlich dass reguläre Ausdrücke und Automaten, also endliche Automaten gleich ausdrucksstark sind.

Also ich kann die gleichen Sprachen durch reguläre Ausdrücke beschreiben wie durch

endliche Automaten. Davon haben sie eine Implikation, nämlich die von den regulären Ausdrücken zu den

Automaten schon in BFS gesehen. Das heißt wir wissen, Automaten sind mindestens so ausdrucksstark

wie reguläre Ausdrücke. Wir zeigen heute, dass das umgekehrt auch gilt. Also das heißt, sie sind

auch nicht ausdrucksstärker als reguläre Ausdrücke. Und wir sehen uns an zunächst mit

so einem relativ fußläufigen Algorithmus, wie man deterministische Automaten minimiert.

Also nicht deterministischen Automaten minimiert man, indem man ihn erst determinisiert und dann

minimiert. Und wir sehen uns also an, wie man schon deterministische Automaten dann noch mal

minimiert. Und wie gesagt, ich mache das erstmal so relativ wissenschaftsfrei, also einfach mal,

wir sehen uns den Algorithmus an und es ist zwar einigermaßen vielleicht auch über den Daumen

erkennbar, dass er korrekt ist. Den tatsächlichen Korrektheitsbeweis liefern wir aber erst am

Donnerstag nach, wenn wir uns nämlich dann ansehen, wie sich die ganze Geschichte in

Begriffen von Codaten darstellt. So wir schließen also an, dann den Recap über

endliche Automaten noch ein über reguläre Ausdrücke. Was ein regulärer Ausdruck ist,

das definieren wir einfach über eine Grammatik. Das heißt, ein regulärer Ausdruck,

metavariablen R oder S, ist entweder 1 oder 0 oder eine Summe von zwei Ausdrücken oder

eine sequenzielle Komposition von zwei Ausdrücken oder eine Iterierung von zwei Ausdrücken,

hier mit dem sogenannten Klinistern oder er ist einfach ein Alphabetsymbol A,

wobei eben dieses A hier aus einem festgewählten Alphabet Sigma stammt,

kennen das dieselbe Rolle spielt, wie eben das Alphabet bei den endlichen Automaten.

So was wir hier sehen, ist also eine Programmiersprache. Wir sehen gleich,

was das so programmiert. Eine sehr einfache und insbesondere ist sie anders als das meiste,

was wir uns angesehen haben. Ich wollte sagen, das meiste, was wir uns angesehen haben,

ist Turing-mächtig, aber gerade zum Beispiel System F ist natürlich nicht Turing-mächtig,

weil es terminierend ist. Das hier ist also noch weniger ausdrucksmächtig. Dafür hat man eben

wesentlich besseren Griff auf die Dinge. Man kann zum Beispiel Äquivalenz von solchen Dingen

entscheiden oder so, was ich für Turing-Maschinen ja nicht kann. Oder ich kann

Operationen an den Dingen vornehmen, wie zum Beispiel eben Minimierung. Das funktioniert

in anderen Bereichen auch schlechter. Das sind die Ausdrücke und die haben eine Semantik.

Die Semantik dieser Ausdrücke ist, sie definieren Sprachen. Also jeder reguläre Ausdruck definiert

eine Sprache, sprich eine Teilmenge von Sigma Stern, also eine Menge von Wörtern.

Die Definition dieser Semantik ist einfach durch Rekursion über unsere Grammatik. Das heißt,

wir sagen einfach, was diese Operationen alle bedeuten. Gut, Null bezeichnet die Leeresprache,

eins dagegen bezeichnet die Sprache, die nur das leere Wort enthält, eine durchaus andere