So, schönen guten Nachmittag. Ich vertrete heute noch mal den Herrn Prof. Schröder,

der ja am Montag, glaube ich, das Thema über Polymorphie und System F so weit abgeschlossen

hat. Wenn man mal von diesem Beweis der Normalisierung absieht, der nächsten Donnerstag dann nachgeschoben

wird. Das Thema der heutigen Vorlesung und auch der nächsten Vorlesung habe ich schon

mal angeschrieben. Es wird um Automaten gehen und reguläre Sprachen. Und da kann man sich

jetzt erstmal fragen, warum machen wir das? Das gibt es doch in BFS schon. Auch in BFS

wurden schon die interessantesten Ergebnisse über diese Automatentheorie, wie zum Beispiel

dieser Kleinesatz, behandelt. Dementsprechend wird es jetzt zunächst auch mal eine Wiederholung

werden von was ist ein Endlicher Automat und was ist ein regulärer Ausdruck. Was uns aber

eigentlich interessiert hier in dieser Vorlesung ist eine koalgebraische Sicht auf Sprachen

bzw. auf Automatentheorie und reguläre Sprachen. Das heißt, wir schauen uns an, wie man solche

Automaten und solche Sprachen als Kodaten formulieren kann. Und ein Ergebnis, das in

dieser Hinsicht dann relativ schön rauskommt, ist die Minimierung von endlichen Automaten,

was in BFS weggelassen wurde. Und zwar aus genau diesem Grund, weil es aus dieser koalgebraischen

Sicht ganz schön rausfällt und das einen schönen Anwendungszweck dieses Teilgebiet

hier bietet. Also fangen wir mal an mit ein paar wiederholenden Definitionen. Also erstmal

gab es diesen Begriff des nicht deterministischen endlichen Automaten, non deterministic finite

automaton. Also man kann das jetzt noch mit dem Epsilon ergänzen, wenn diese Automaten

Epsilonübergänge haben, aber das interessiert uns jetzt vorher erstmal nicht. Und so ein

Automat, den nenne ich mal A, ist ein Fünftupel, auch wie in BFS, bestehend aus den Zuständen

Q, einer Alphabetenmenge Sigma, eine Zustandsübergangsfunktion Delta, die schreibe ich jetzt hier Großdelta,

wir werden dann nachher noch sehen warum, einem Startzustand und einer Menge von Endzuständen.

Also um das mal kurz nochmal alles niederzuschreiben, das ist eine endliche Menge von Zuständen.

Also dafür das Finite in dem NFA, das Sigma ist ebenfalls eine endliche Menge und die

nennen wir das Alphabet, auch bekannt. Und dann haben wir hier jetzt in diesem nicht

deterministischen Fall eine Zustandsübergangsfunktion, die jedem Zustand eine Menge von Folgezuständen

zuweist unter den Eingabebuchstaben. Das heißt, wir haben hier eine Menge, also Potenzmenge

von Pan, Sigma, Kreuz, Q. Also das ist eine Menge von Pan aus einem Alphabetsbuchstaben

und einem Folgezustand. Also für jeden Alphabetsbuchstaben bekommen wir eventuell einen Folgezustand

oder eben auch nicht, wir können auch in einem Deadlock stecken bleiben. Ja und wir

schreiben dann eben abkürzend solche Übergänge, genau dann wenn das Paar a Q' in Delta von

Q enthalten ist. Dann das S ist einfach nur ein Element der Zustandsmenge, das ist der

Startzustand oder initiale Zustand oder Anfangszustand und unser F ist eine Teilmenge von Q und kennzeichnet

einfach die Zustände, die akzeptierend sind, also finale oder akzeptierende Zustände.

So, also das sind jetzt die Daten von so einem Automaten und was macht der Automat? Der akzeptiert

Wörter aus diesem Alphabet bzw. aus der Menge Sigma Stern von Wörtern über diesem Alphabet

also für ein Wort W in Sigma Stern gilt zunächst mal entweder, zunächst mal dass das leere Wort

immer in den Zustand auf sich selbst überführt und jetzt induktiv wenn wir mit diesem W,

also wenn wir vorne an dieses W noch einen Buchstaben aus Sigma hinzufügen, dann geht

Q mit diesem zusammengesetzten Wort nach Q' über genau dann wenn es noch einen Zwischenzustand

gibt Q', sodass Q mit a nach Q' übergeht und das geht ja direkt aus dieser Delta Übergangsfunktion

hervor und induktiv dann eben mit W nach Q'. Und wann gilt so ein Wort dann als akzeptiert

vom Automaten? Also das beschreiben wir so, dass W in der Sprache des Automaten ist L von a und

es ist genau dann der Fall wenn es einen Zustand Q gibt, sodass man das der in der Menge F,

also der akzeptierenden Zustände ist und es einen Weg gibt von S mit diesem Wort W nach Q zu kommen.

So das war jetzt die allgemeinere nicht deterministische Variante aber wir interessieren

uns auch sehr oft für die deterministische Variante die DFAs. Da ist die Einschränkung eben,

dass für alle Zustände in diesem Automaten und für alle Buchstaben aus dem Eingabealphabet

ein eindeutiger Nachfolgezustand existiert. Also ein Q' existiert mit Q mit a über. Also das heißt

dieser DFA der kann nicht stecken bleiben und er hat auch keine Auswahl. Dementsprechend schreiben