Das Thema Grammatiken soll zunächst im Skript nicht behandelt werden, damit ein gutes Kapitel zu den schwierigen Turing-Maschinen und der Komplexitätstheorie entstehen kann. Für die nicht ganz so komplizierten Grammatiken sei auf die Folien und bei Bedarf auf das Buch von Hopcroft, Ullman und Motwani verwiesen.

Eine kurze Übersicht über den behandelten Stoff wollen wir an dieser Stelle aber geben. Wenn einem das alles etwas sagt und man damit arbeiten kann, dann kennt man sich in diesem Teil gut aus.

Wir haben zunächst die Grammatik eingeführt. Dort waren dann noch die Begriffe Nonterminal, Terminal, Produktion und Startsymbol wichtig. Diese beschreiben quasi was eine Grammatik ist. Um auch zu beschreiben, was man mit einer Grammatik machen kann, waren dann die Begriffe Ableitung und (Generierte) Sprache wichtig und nebenher noch der Begriff der Äquivalenz.

Dann haben wir die Grammatiken eingeschränkt und haben die kontextfreie Grammatik (oder auch Typ-2-Grammatik) und die rechtslineare Grammatik (auch Typ-3-Grammatik) eingeführt. Bei kontextfreien Grammatiken traten dann noch die Begriffe \(\lambda\)-Produktion und \(\lambda\)-frei auf.

Für die kontextfreien Grammatiken haben wir die Sprachfamilie CF (context free) eingeführt.

Wir haben dann zwei Konstruktionstechniken für Grammatiken kennengelernt, Abschlusseigenschaften der Sprachfamilie CF betrachtet und gesehen, dass rechtslineare Grammatiken und DFAs äquivalent sind sowie erwähnt, dass kontextfreie Grammatiken und Kellerautomaten äquivalent sind.

Dann haben wir die Chomsky-Normalform kennengelernt und ein Verfahren betrachtet, wie man diese herstellen kann. Im ersten Schritt dieses Verfahrens war zudem ein Test enthalten, mit dem man testen kann, ob \(\lambda \in L(G)\) gilt und im dritten Schritt war ein Verfahren enthalten, mit dem man eine Grammatik reduzieren kann.

Zum Schluss haben wir dann noch das Pumping Lemma für kontextfreie Sprachen kennengelernt und damit gezeigt, dass es Sprachen gibt, die nicht kontextfrei sind.

 
Mittlerweile haben wir mit DFAs, NFAs, \(\lambda\)-NFAs und regulären Ausdrücken vier verschiedene Formalismen kennen gelernt, die die Familie der regulären Sprachen erfassen, d.h. jede von einem dieser drei Automatenmodelle akzeptierte und jede von einem regulären Ausdruck beschriebene Sprache, ist eine reguläre Sprache. Wir haben dann noch die Abschlusseigenschaften kennengelernt und gesehen, dass es auch gar nicht so leicht ist, keine reguläre Sprache mehr zu haben. Vereinigt man z.B. zwei reguläre Sprachen, so hat man wieder eine, ebenso beim Durchschnitt und auch das Komplement einer regulären Sprache ist stets regulär.

Es erscheint aber unwahrscheinlich, dass alle Sprachen regulär sind. Der DFA kann ja nur endlich viele Informationen speichern und sich auch keine Informationen mehrmals ansehen. Intuitiv kann man also gut vermuten, dass es doch Sprachen geben sollte, die nicht regulär sind. Aber wie könnte eine solche Sprache aussehen? Und wie beweist man, dass eine Sprache tatsächlich nicht regulär ist?

Da ein endlicher Automat nur endlich viele Informationen speichern kann, sollten wir dann an die Grenzen endlicher Automaten stossen, wenn wir uns unendlich viele Informationen merken müssen bzw. zwar endlich viele, aber von der Länge des Eingabewortes abhängig viele Informationen. Müssten wir uns z.B. bei einem Eingabewort der Länge \(10\) gerade \(10\) Informationen merken, bräuchten wir \(10\) Zustände. Ist das dann aber auch für ein Eingabewort der Länge \(100\) und \(1000\) nötig, dann gibt es keine obere Grenze für die Zustände und es kann keinen endlichen Automaten für die Sprache geben.

Ein guter Kandidat ist daher vielleicht die Sprache \(L = \{a^n b^n \mid n \in \mathbb{N}\}\). Diese Sprache ist nicht zu kompliziert zu beschreiben und dennoch erfüllt sie intuitiv obiges. Wenn wir nämlich die \(n\) \(b\)s lesen wollen, so müssen wir uns vorher die Zahl \(n\) merken, also die Anzahl der gelesenen \(a\)s und diese Zahl ist wie oben gewünscht abhängig von der Wortlänge. Wir müssten einen Zustande haben, in dem wir uns merken, dass wir ein \(a\) gelesen haben, einen, in dem wir uns merken, dass es zwei waren usw. Da die Zahl beliebig groß werden kann, kann es intuitiv keinen DFA geben, der sich alle diese Zahlen in seinen nur endlich vielen Zuständen merkt.

Dies ist aber zunächst nur eine Intuition. Wie beweisen wir nun, dass obiges \(L\) tatsächlich nicht regulär ist? Hier hilft uns das sogenannte Pumping Lemma.

Das Pumping Lemma

Das Pumping Lemma macht eine Aussage über alle regulären Sprachen, d.h. es beschreibt eine Eigenschaft, die alle regulären Sprachen haben. Hat eine Sprache diese Eigenschaft also nicht, so kann sie nicht regulär sein. Um uns dem Pumping Lemma zu nähern, machen wir uns einmal selbst auf die Suche nach einer Eigenschaft \(X\), die jede reguläre Sprache haben muss. Wir wissen bisher von regulären Sprachen, das es zu jeder reglären Sprache einen DFA gibt, der sie akzeptiert. Von DFAs wiederum wissen wir, dass sie nur endlich viele Zustände haben. Dies können wir versuchen auszunutzen.

Legt man einem Automaten mit \(n\) Zuständen ein Wort vor, dass z.B. die Länge \(4 \cdot n\) hat, dann muss der Automat, wenn er das Wort akzeptiert, mindestens einen Zustand mehrfach besuchen. Bei jedem gelesene Symbol findet ja ein Zustandswechsel statt und wenn man \(4 \cdot n\) Symbole liest, finden also \(4 \cdot n\) Zustandswechsel statt. Hat man nur \(n\) Zustände zur Auswahl muss zwangsläufig mindestens einer mehrfach auftreten. Das heißt auch, dass beim Lesen des Wortes der Automat Schleifen durchwandert. Diese Schleifen könnte man mehrfach entlang gehen und so neue Worte erzeugen, die alle auch in der Sprache sein müssten. Damit haben wir eine schöne Eigenschaft regulärer Sprachen gefunden. Für alle Worte der Sprache ab einer bestimmten Länge muss gelten, dass man sie so zerlegen kann, dass ein Teilstück des Wortes beliebig oft wiederholt werden kann und das Wort dennoch weiterhin in der Sprache ist.

Hätte man für \(L\) einen Automaten mit \(k\) Zuständen, dann betrachtet man \(a^k b^k\). Nach obigem müsste schon beim Lesen der ersten \(k\) Symbole (also der \(a\)s) ein Zustand mehrfach auftreten, d.h. wir haben dann bereits beim Lesen der \(a\)s eine Schleife und könnten diese Schleife auch mehrfach entlang gehen. Nach obigem Überlegungen müssten die dabei entstehenden Wort ja alle in der Sprache \(L\) sein (da sie ja weiterhin von unserem angenommenen Automaten akzeptiert werden müssten). Dies klappt aber nicht, da wir ja Worte der Art \(a^{k+j} b^k\) erzeugen würden, die gerade nicht in \(L\) sind.

Die oben erarbeitete Vorstellung der speziellen Eigenschaft aller regulären Sprachen wird nachfolgend im Pumping Lemma formalisiert und bewiesen. Im Beweis finden sich etliche der oben schon angedeuteten Argumente wieder. Im Anschluss an den Beweis nutzen wir das Pumping Lemma dann, um für \(L = \{a^n b^n \mid n \in \mathbb{N}\}\) eindeutig nachzuweisen, dass diese Sprache nicht regulär ist. Auch in dem Beweis finden sich dann die Überlegungen von eben als überzeugende Argumente wieder.

Bevor wir zum Beweis kommen, betrachten wir das Lemma noch einmal genauer. Wie oben in den Überlegungen schon beschrieben, macht es eine Aussage über reguläre Sprachen. Wenn eine Sprache also regulär ist, dann gilt das Pumping Lemma. Es sagt dann, dass es eine natürliche Zahl \(n \geq 1\) gibt derart, dass jedes Wort \(z\) aus \(L\), das mindestens die Länge \(n\) hat, zerlegt werden kann in \(z = uvw\).

 
Die Zerlegung \(z = uvw\) aus dem Pumping Lemma erfüllt dann drei Eigenschaften, von denen wir die dritte oben bereits skizziert haben: Man kann einen Teil des Wortes (hier das \(v\)) beliebig oft schreiben und erhält stets ein Wort aus \(L\). Das Wort \(v\) entspricht im Automaten aus den vorherigen Überlegungen der Schleife. Dies wird auch gleich im Beweis deutlich werden. Die erste und zweite Eigenschaft besagen, dass die Schleife existieren muss, also mindestens die Länge \(1\) haben muss (zweite Eigenschaft) und dass diese bis zu einem bestimmten Zeitpunkt das erste Mal entlang gegangen sein muss (erste Eigenschaft). Die erste Eigenschaft rührt daher, dass bei einem Automaten mit \(n\) Zuständen nach \(n\) gelesenen Symbolen bereits \(n+1\) Zustände besucht wurden (der Startzustand und nach jedem gelesenen Symbol ein weiterer). Hat man nur \(n\) Zustände ist spätestens der \(n+1\)-te Zustand also ein Zustand, den man schon einmal besucht hatte.

Man beachte noch, dass die dritte Eigenschaft besagt, dass mit \(z = uvw \in L\) für jedes \(i \geq 0\) auch \(uv^iw \in L\) gilt. Insbesondere kann \(i\) auch \(0\) sein und in diesem Fall haben wir \(uv^0w = uw\). Es müssen also \(uw\) ebenso wie \(uvvw\), \(uvvvw\) usw. alle in \(L\) sein.

Wir beweisen nun das Pumping Lemma. Man achte beim Durcharbeiten darauf, wo sich die obigen Ideen überall wiederfinden.

Wir wollen nun das Pumping Lemma nutzen, um zu zeigen, dass die Sprache \(\{a^n b^n \mid n \in \mathbb{N}\}\) nicht regulär ist. Dazu nehmen wir an, die Sprache wäre regulär und zeigen einen Widerspruch. Wir führen den Beweis zunächst sehr ausführlich und bauen etliche Erklärungen in den Beweis ein. Wir betonen aber schon hier, dass wir bei einem Widerspruchsbeweis annehmen, dass das Pumping Lemma gilt und dann einen Widerspruch herstellen wollen. Da das Pumping Lemma sagt, dass alle Worte mit \(z \in L\) und \(|z| \geq n\) zerlegt werden können, genügt es für ein Wort mit \(z \in L\) und \(|z| \geq n\) zu zeigen, dass dem nicht so ist. Da das Pumping Lemma dann sagt, dass eine Zerlegung \(z = uvw\) existiert, die die drei Eigenschaften erfüllt (also erstens \emph{und} zweitens und drittens), muss man dann zeigen, dass jede Zerlegungen von \(z\) in \(uvw\) mindestens eine der drei Eigenschaften nicht erfüllt (also alle Zerlegungen im Widerspruch zu erstens, zweitens oder drittens stehen).

 
Damit haben wir nun gezeigt, dass es tatsächlich Sprachen gibt, die nicht regulär sind! Wir betonen dies im folgenden Satz.

Das Pumping Lemma hilft uns für Sprachen wie obige und auch für weitere zu zeigen, dass die Sprachen nicht regulär sind. Das Pumping Lemma macht also eine Aussage über eine Eigenschaft, die alle regulären Sprachen haben. Es wird dann aber benutzt, um gerade zu zeigen, dass eine Sprache nicht regulär ist.

Wir fassen noch einmal den Ablauf zusammen, wenn man für eine Sprache \(L\) mittels Nutzung des Pumping Lemmas zeigen will, dass \(L\) nicht regulär ist.

1. Annehmen \(L\) wäre regulär
2. Die Zahl aus dem Pumping Lemma benennen (z.B. \(k\)).
3. Ein Wort \(z\) finden mit \(|z| \geq k\) und \(z \in L\).
• Dieses Wort muss gut gewählt sein, damit der nachfolgende Widerspruch gelingt. Hier muss man also u.U. experimentieren.
4. Für alle Zerlegungen von \(z\) in \(uvw\) zeigen, dass sie
   im Widerspruch zur ersten, zweiten oder dritten Bedingung sind.
   • Üblicherweise betrachtet man alle Zerlegungen, die die erste und zweite Bedingung erfüllen und zeigt, dass man dann einen Widerspruch zur dritten Bedingung erhält.
5. Also: Alle Zerlegungen \(z = uvw\) mit \(|uv| \leq k\) und \(|v| \geq 1\) betrachten.
6. Zeigen, dass man ein \(i\) findet mit \(u v^i w \not\in L\). (Dies kann auch \(i = 0\) sein!)

Wir wollen zum Abschluss noch ein zweites Beispiel betrachten und hier beim Beweis zügig vorgehen. Zur Erinnerung: \(w^{rev}\) ist gerade das Wort \(w\) von hinten nach vorne gelesen, also z.B. \(011^{rev} = 110\).

Man beachte, dass der obige Beweis mit \(z = 0^k 0^k\) nicht gelungen wäre. Die Wahl des Wortes ist also wichtig.

 
In diesem Abschnitt wollen wir uns mit Abschlusseigenschaften der regulären Sprachen, d.h. mit der Frage, ob, gegeben eine Operation \(\circ\) und zwei reguläre Sprachen \(L_1, L_2\), auch \(L_1 \circ L_2\) regulär ist. \(\circ\) könnte z.B. die Vereinigung sein oder als Operation auf nur eine Menge, die Operation, die an jedes Wort aus \(L_1\) ein \(a\) anfügt.

Abschlusseigenschaften erlauben oft Einblicke in Sprachfamilien und helfen auch oft beim Konstruieren von z.B. speziellen Automaten oder beim Beweis, dass es keinen Automat für eine Sprache geben kann.

Weitere Formalismen für REG

Bevor wir zu den Abschlusseigenschaften kommen, wollen wir vorher noch zwei weitere Formalismen einführen, die wie DFAs und NFAs gerade die Sprachfamilie der regulären Sprachen erfassen. Wir wollen diese Formalismen nur einführen und benutzen. Die Beweise, dass sie tatsächlich äquivalent zu DFAs sind werden wir nicht führen. Man findet diese Beweise bspw. in dem Buch von Hopcroft, Motwani und Ullman aus der Literaturliste.

NFAs mit \(\lambda\)-Kanten

Man kann einem NFA zusätzlich zu dem bisherigen noch erlauben, \(\lambda\)-Kanten (auch \(\epsilon\)-Kanten genannt) zu benutzen. Diese Kanten sind also statt mit einem Symbol mit dem leeren Wort beschriftet. Die Bedeutung dahinter ist dann auch, dass man nichts vom Eingabeband liest (also quasi das leere Wort vom Eingabeband liest), der Lesekopf auf dem Eingabeband also nicht weiter bewegt wird. Ein Zustandswechsel findet allerdings statt.

In dem abgebildeten Beispiel kann der NFA zuerst ohne ein Symbol zu lesen mittels der \(\lambda\)-Kanten nach \(z_1\) oder \(z_3\) wechseln. Dort arbeitet er dann weiter. Auf dem Wort \(11\) gibt es dann beispielsweise vier verschiedene Rechnungen (in \(z_1\) bleiben, in \(z_3\) bleiben, einmal in \(z_1\) eine \(1\) lesen und dann nach \(z_2\) wechseln und mit der ersten \(1\) nach \(z_2\) wechseln und dort blockieren). Da eine dieser Rechnungen \((z_0, 11) \vdash (z_1, 11) \vdash (z_1, 1) \vdash (z_2, \lambda)\) eine Erfolgsrechnung ist, akzeptiert der NFA. Man beachte, dass bei dem ersten Konfigurationsübergang \((z_0, 11) \vdash (z_1, 11)\) kein Symbol gelesen wird, aber ein Zustandsübergang stattfindet.

Das Beispiel ist zwar recht einfach gewählt, dennoch sollte man sich nicht täuschen lassen. Diese Kanten können äu{\ss}erst nützlich sein. Beim Entwurf von Automaten, erleichtern sie einem wieder an vielen Stellen die Arbeit und bei Beweisen, helfen sie oft Argumente zu vereinfachen.

Man müsste nun noch Begriffe wie Überführungsfunktion, Rechnung, Konfigurationsübergang usw. anpassen. Wir wollen dies hier nicht tun und das Modell einfach informal benutzen. Wir nennen diesen Automaten dann einen NFA mit \(\lambda\)-Kanten oder auch kürzer einen \(\lambda\)-NFA.

Wir betonen noch den folgenden wichtigen Satz:

Der Satz besagt, dass DFAs, NFAs und \(\lambda\)-NFAs äquivalent sind. Die Familie der regulären Sprachen wird also von jedem dieser drei Modelle erfasst. Auf einen Beweis dieses Satzes wollen wir hier verzichten. Man findet ihn z.B. in dem Buch von Hopcroft, Motwani und Ullman aus der Literaturliste.

Reguläre Ausdrücke

Wir wollen nun noch einen vierten Formalismus einführen, mit dem wir ebenfalls die Familie der regulären Sprachen erfassen. Dies sind die sogenannten regulären Ausdrücke.

Ein paar Beispiele für reguläre Ausdrücke, wobei \(\equiv\) hier für „beschreibt die Menge“ steht:

• \((a+b)^* \equiv (\{a\} \cup \{b\})^* = \{a,b\}^*\)
• \((a \cdot b) \equiv \{a\} \cdot \{b\} = \{ab\}\)
• \(a \cdot b^* + b \cdot a^* \equiv \{a\}\cdot\{b\}^* \cup \{b\}\cdot\{a\}^*\)
• \(\emptyset^* \equiv \emptyset^* = \{\lambda\}\)
• Worte, die auf \(1\) enden: \((0+1)^* \cdot 1\)
• Worte, die \(00\) oder \(11\) enthalten: \((0+1)^* \cdot (00 + 11) \cdot (0+1)^*\)

Reguläre Ausdrücke und die Mengenoperationen sind also recht ähnlich. Mit regulären Ausdrücken spart man sich aber oft eine Menge Klammern. Daneben wollen wir auch die üblichen Regeln zur Klammerersparnis nutzen wie \(\cdot\) vor \(+\) und die hochgestellten \(+\) und \(*\) vor \(\cdot\).

Aufgrund der Ähnlichkeit, wollen wir dann reguläre Ausdrücke gleich wie Mengen nutzen und z.B. \(aaa \in a^*\) erlauben. Gemeint ist dann mit dem regulären Ausdruck in diesem Kontext gerade die Menge, die er beschreibt.

Man kann nun wieder zeigen, dass es zu jedem regulären Ausdruck \(R\) einen DFA \(A\) gibt, der gerade die von \(R\) beschriebene Menge akzeptiert und dass es zu jedem DFA \(A\) eine regulären Ausdruck gibt, der gerade \(L(A)\) beschreibt. Auch hier wollen wir reguläre Ausdrücke der Definition entsprechend benutzen, den eben angesprochenen Beweis jedoch nicht führen. Er findet sich wieder in der Literatur.

Insgesamt haben wir damit folgenden Satz:

Abschlusseigenschaften

Wir wollen uns nun damit beschäftigen, ob die regulären Sprachen gegenüber bestimmten Operationen abgeschlossen sind. Betrachten wir als Operation z.B. die Vereinigung, dann interessiert uns die Frage, ob \(L_1 \cup L_2 \in REG\) ist, wenn \(L_1, L_2 \in REG\) gilt. Gilt dies stets, so sagt man die Sprachfamilie der regulären Sprachen ist gegenüber Vereinigung abgeschlossen. Die Bezeichnung rührt daher, dass man mittels dieser Operation dann quasi nicht aus der Familie der regulären Sprachen herauskommt.

Um den Abschluss genauer zu formulieren, definieren wir:

Man kann dies auch allgemeiner für Mengen und Operationen auf diesen Mengen einführen. Die Menge der natürlichen Zahlen ist dann z.B. gegenüber der Addition abgeschlossen, da die Summe zweier natürlicher Zahlen wieder eine natürliche Zahl ist. Die natürlichen Zahlen sind hingegen nicht gegenüber der Subtraktion abgeschlossen, da es zwar natürliche Zahlen gibt, die subtrahiert voneinander wieder eine natürliche Zahl ergeben, aber eben auch welche, bei denen das nicht passiert (wobei es hier primär auf die Reihenfolge ankommt, aber die dürfte man sich ja auch nicht aussuchen, sonst hätte man eine andere Operation).

Einfache Abschlusseigenschaften

Wir wollen nun für einige Operationen zeigen, dass die regulären Sprachen gegenüber ihnen abgeschlossen sind. Die ersten vier Operationen kriegen wir fast geschenkt.

Wir haben für diese vier Operationen also gar nicht viel zu tun gehabt. Wir müssen hier lediglich beachten, dass jede durch einen regulären Ausdruck beschriebene Menge eine reguläre Sprache ist. Dann benutzen wir noch die Operationen, die wir bei regulären Ausdrücken syntaktisch haben und sind schon fertig.

Komplementbildung

Schwieriger ist da schon zu zeigen, dass die regulären Sprachen gegenüber Komplementbildung abgeschlossen sind.

In \(\overline{L}\) sind also gerade all jene Worte aus \(\Sigma^*\), die nicht in \(L\) sind. Die Worte, die in \(L\) sind, sind gerade nicht in \(\overline{L}\).

Sind die regulären Sprachen nun gegenüber Komplementbildung abgeschlossen? Wir können zumindest nicht so vorgehen wie bei dem vorherigen Satz. Dort nutzten wir reguläre Ausdrücke. Das ist hier nicht so leicht möglich, da sich in der Definition der regulären Ausdrücke keine Operation findet, mit der wir Komplement ausdrücken könnten.

Mit regulären Ausdrücken kommen wir tatsächlich nicht gut weiter. Wohl aber mit Automaten! Haben wir einen Automaten \(A\) für eine Sprache \(L\), dann wollen wir jetzt also erreichen, dass ein Wort, das \(A\) akzeptiert hat, nicht mehr akzeptiert wird und ein Wort, das \(A\) nicht akzeptiert hat, nun akzeptiert wird. Dies erreichen wir gerade, indem wir Zustände, die keine Endzustände sind, zu solchen machen und umgekehrt. Endeten wir dann vorher in einem normalen Zustand (und akzeptierten also nicht), so enden wir jetzt in einem Endzustand (und akzeptieren also), endeten wir vorher in einem Endzustand (und akzeptierten also), so enden wir nun in einem normalen Zustand (und akzeptieren also nicht). Auf eine Kleinigkeit müssen wir noch achten. Damit dies funktioniert, muss \(A\) auch tatsächlich jedes Wort lesen können. Kann er ein Wort nämlich nicht zu Ende lesen, so wird das Wort nicht akzeptiert. Unser neuer Automat kann das Wort dann aber weiterhin nicht zu Ende lesen und akzeptiert also auch nicht. Wir müssen also dafür sorgen, dass \(A\) jedes Wort lesen kann. Dies erreichen wir ganz einfach dadurch, dass wir gleich zu Beginn von einem vollständigen DFA \(A\) für \(L\) ausgehen, der ja ebenfalls stets existiert. Wir fassen den Beweis noch einmal zusammen.

Durchschnittsbildung

Als nächstes wenden wir uns dem Durchschnitt oder dem Produkt zweier Sprachen zu, d.h. der Operation \(L_1 \cap L_2\).

Dies lässt sich mit unserem bisherigen Wissen sehr schnell zeigen. Wenn man bedenkt, dass \(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\) nach dem Gesetz von de Morgan gilt, dann sind wir sofort fertig, da wir ja schon wissen, dass die regulären Sprachen gegenüber Komplement und Vereinigung abgeschlossen sind. (Sind also \(L_1\) und \(L_2\) regulär, dann ist auch \(\overline{L_1}\) und \(\overline{L_2}\) und damit auch \(\overline{L_1} \cup \overline{L_2}\) und damit letztendlich \(\overline{\overline{L_1} \cup \overline{L_2}}\) regulär, was gerade \(L_1 \cap L_2\) ist.)

Es gibt aber eine sehr schöne Methode, wie man dies direkt mit Automaten machen kann. Wir wollen dies hier einmal tun und dabei den Produktautomaten zu zwei Automaten \(A_1\) und \(A_2\) kennenlernen. Dieser akzeptiert gerade dann ein Wort, wenn \(A_1\) und \(A_2\) dieses Wort beide akzeptieren. Damit akzeptiert der Produktautomat also gerade den Schnitt von \(L(A_1)\) und \(L(A_2)\).

Erinnern wir uns an die Potenzautomatenkonstruktion. Hier haben wir uns im Zustand des konstruierten DFAs gemerkt, in welchen Zuständen der ursprüngliche NFA nichtdeterministisch sein kann. Hier können wir ähnlich vorgehen. Allerdings wollen wir uns genau merken, welcher Zustand zum ersten und welcher Zustand zum zweiten Automaten gehört. Wir arbeiten daher mit Tupeln \((z_1, z_2)\) als neue Zustände von \(C\), wobei im ersten Tupelelement ein Zustand von \(A_1\) und im zweiten Tupelelement ein Zustand von \(A_2\) notiert wird. Ein Übergang mit Symbol \(a\) geschieht dann genau dann, wenn im ersten Tupelelement (also im Automaten \(A_1\)) ein Übergang mit \(a\) möglich ist und ebenso im zweiten Tupelelement (also im Automaten \(A_2\)). Wenn \(C\) dann ein Wort \(w\) liest, dann macht er im ersten Tupelelement seiner Zustände quasi eine Rechnung von \(A_1\) und im zweiten eine von \(A_2\). Akzeptieren soll er daher genau dann, wenn im ersten Tupelelement ein Endzustand von \(A_1\) und im zweiten Tupelelement ein Endzustand von \(A_2\) ist. So ist sichergestellt, dass beide Automaten gleichzeitig in einem Endzustand sind, also beide das Wort \(w\) akzeptieren. Dies ist gerade, was wir für \(C\) erreichen wollen. \(C\) soll akzeptieren, wenn \(A_1\) \emph{und} \(A_2\) akzeptieren und sonst ablehnen. Wir formalisieren die Konstruktion jetzt genauer.

Noch eine Anmerkung zur Konstruktion: Wenn man den Produktautomaten konstruieren will (oder einen Algorithmus dafür implementieren will), dann verfährt man wieder so wie beim Potenzautomaten und beginnt nicht sofort mit \(Z_3 = Z_1 \times Z_2\), sondern beginnt mit dem Startzustand \(z_{3,0} = (z_{1,0}, z_{2,0})\) und konstruiert dann sukzessive die initiale Zusammenhangskomponente.

Spiegelworte

Zuletzt wollen wir einen Blick auf Spiegelworte werfen. Spiegelworte sind Worte, die sich durch rückwärts Lesen eines ursprünglichen Wortes ergeben. Ist z.B. \(w = 011\), dann ist das Spiegelwort \(w^{rev} = 110\). Wir definieren dies formal mittels einer induktiven Definition.

 
Wir können nun zeigen, dass die regulären Sprachen gegenüber der \(rev\)-Operation abgeschlossen sind.

Mit diesem Resultat können wir dann endlich auch schlussfolgern, dass die komplizierte Sprache $$ Sum = \{ w \in \Sigma^* \mid \text{ die unterste Zeile ist Summe der oberen Zeilen} \} $$ tatsächlich regulär ist (zur Erinnerung: die Symbole in \(\Sigma\) waren im Grunde Vektoren der Länge \(3\) also z.B. \((0,0,1)\) als Spalte geschrieben). Bisher hatten wir ja nur gezeigt, dass \(Sum^{rev}\) regulär ist.

 
Nachdem wir den NFA nun eingeführt haben, macht es Sinn, dass wir uns als nächstes gleich die Frage stellen, in welchem Verhältnis er zum DFA steht? Kann der DFA mehr als der NFA? Kann der NFA mehr als der DFA? Können beide das gleiche? Sind sie unvergleichbar?

Mehr zu „können“ bezieht sich hierbei auf die akzeptierten Sprachen. Der NFA kann dann mehr als der DFA, wenn es zu jeder Sprache \(M\), zu der es einen DFA gibt, der \(M\) akzeptiert, auch einen NFA gibt, der \(M\) akzeptiert, und ferner, wenn es eine Sprache \(M‘\) gibt, für die zwar ein NFA konstruiert werden kann, aber kein DFA.

Was man recht schnell sehen kann, ist, dass jeder DFA auch als spezieller NFA angesehen werden kann, der NFA also mindestens all das kann, was der DFA kann. Seine spezielle Fähigkeit zu einem Buchstaben mehrere Kanten aus einem Zustand heraus zu haben, brauch der NFA ja gar nicht benutzen und ist dann im Grunde ein DFA. Will man dies formal ausführen, so sei \(\delta_D\) die Überführungsfunktion eines DFA und \(z_0\) sein Startzustand. Man setzt dann $$ \delta_N(z,x) := \{\delta_D(z,x)\} $$und $$ Z_{start} := \{z_0\} $$für die Überführungsfunktion \(\delta_N\) und die Startzustandsmenge \(Z_{start}\) des NFA. Zustandsmenge, Eingabealphabet und Endzustandsmenge übernimmt man für den NFA. Ist \(A\) der DFA und \(B\) der so konstruierte NFA, so kann man \(L(A) = L(B)\) sehr einfach zeigen, da im Grunde genau das gleiche passiert, nur das in der erweiterten Überführungsfunktion im ersten Argument einmal ein Zustand steht (beim DFA) und einmal eine einelementige Menge mit gerade diesem Zustand (beim NFA).

Die spannende Frage ist nun also, ob es auch andersherum geht, ob man also zu jedem NFA \(A\) einen DFA \(B\) konstruieren kann mit \(L(A) = L(B)\) oder ob es eine Sprache gibt, die ein NFA akzeptieren kann, aber kein DFA.

Wenn wir noch einmal die Arbeitsweise des NFA betrachten, dann stellen wir fest, dass der NFA stets (nichtdeterministisch) in einer Menge von Zuständen sein kann, also in einer Teilmenge seiner Zustandsmenge. Dies erkennt man auch gut an der erweiterten Überführungsfunktion, bei der im ersten Argument ja gerade diese Menge an Zuständen gesammelt wird.

Sei \(Z\) die Zustandsmenge des NFA, dann gibt es gerade \(2^{|Z|}\) viele Teilmengen von \(Z\). Dies sind zwar recht viele, aber es sind endlich viele! Erinnern wir uns an die Konstruktionsmethoden für DFAs, so könnte ein vielversprechender Ansatz also sein, sich in den Zuständen des DFAs gerade diese Teilmengen der Zustände des NFAs zu merken. Die Übergänge könnten dann gerade so gelingen, wie wir dies beim NFA machen, soll heißen: Wenn wir beim NFA \(\hat{\delta}(M,xw) = \hat{\delta}(M‘,w)\) haben, so wechseln wir im DFA aus dem Zustand, in dem wir uns gemerkt haben, dass der NFA nichtdeterministisch in den Zuständen aus \(M\) ist, nun in den Zustand, in dem wir uns dies für \(M‘\) merken. Genau dies passiert ja beim NFA. Vor dem Lesen von \(x\) ist er nichtdeterministisch in den Zuständen aus \(M\), danach nichtdeterministisch in den Zuständen aus \(M‘\). Diese Übergänge lassen sich dann also durch die Überführungsfunktion des NFA ermitteln.

Als Startzustand macht dann die Menge der Startzustände des NFA Sinn, denn in diesen Zuständen ist der NFA ja zu Anfang nichtdeterministisch. Bleibt die Endzustandsmenge zu definieren. Da wir im NFA dann akzeptieren, sobald in der Menge, in der der NFA sich nichtdeterministisch befindet, am Ende ein Endzustand ist, könne wir versuchen im DFA all jene Zustände zu Endzuständen zu machen, in denen wir uns eine Menge \(M\) merken, in der gerade ein Endzustand ist.

Mit diesen Überlegungen können wir zu jedem NFA einen DFA konstruieren und tatsächlich kann man beweisen, dass diese Konstruktion das Gewünschte leistet. Wir fassen die Konstruktion nun noch einmal formal zusammen, machen dann ein Beispiel und zeigen dann, dass die Konstruktion korrekt ist.

Beispiel

Betrachten wir die formale Konstruktion noch einmal. Die Menge der Zustände \(Z'\) des DFA ist gerade die Menge aller Teilmengen der Zustandsmenge \(Z\) des NFA. Ist also z.B. \(\{z_0, z_1\} \subseteq Z\), so ist diese Menge von Zuständen des NFA nun ein einzelner Zustand des DFA. Das Eingabealphabet wurde einfach übernommen, da ja weiterhin die gleichen Symbole gelesen werden sollen. Der Startzustand des DFA ist gerade die Menge der Startzustände des NFA (denn in einem dieser Zustände startet ja jede Rechnung des NFA) und die Endzustände des DFA sind all jene Mengen von Zuständen des NFA, die mindestens einen Endzustand des NFA enthalten (denn endet eine Rechnung des NFA in einem Endzustand, d.h. befindet sich in der Menge der Zustände, in denen er sich nichtdeterministisch nach Lesen eines Eingabewortes befindet, ein Endzustand, so akzeptiert er und dann soll auch der DFA akzeptieren). Um die Überführungsfunktion des DFA zu definieren, werden alle Zustände in der aktuellen Menge \(M\) für ein Symbol \(x\) durchgegangen und für jeden dieser Zustände die Menge der möglichen Nachfolgezustände im NFA ermittelt. Alle diese Mengen werden dann vereinigt und ergeben den Nachfolgezustand im DFA.

Betrachten wir als Beispiel den gezeigten NFA.

Um den DFA zu konstruieren, genügt es, die initiale Zusammenhangskomponente zu bestimmen, d.h. wir beginnen beim Startzustand des DFA und konstruieren für jedes Symbol \(x \in \Sigma\) die Nachfolgezustände. Bei diesen machen wir dann so lange weiter, bis keine neuen Zustände mehr generiert werden. Wir beginnen also mit dem Startzustand \(z_0 := Z_{start}\).

 

Wir wählen nun den Zustand \(\{z_0\}\) des DFA und gehen alle Zustände der Menge durch (hier ist dies zunächst nur der Zustand \(z_0\)). Dann ermitteln wir für das erste Symbol (z.B. \(a\)) die Nachfolgezustände im NFA. Wegen \(\delta(z_0,a)= \{z_0, z_1\}\) ist dies die Menge \(\{z_0,z_1\}\), die dann also der Nachfolgezustand von \(\{z_0\}\) im DFA ist. Entsprechend gelangen wir mit \(b\) zu \(\{z_0\}\).

  

Mit dem Zustand \(\{z_0\}\) sind wir nun fertig, aber wir haben einen neuen Zustand generiert und machen mit diesem wie eben weiter. Wir halten also ein Symbol \(x\) des Eingabealphabets fest, gehen dann bei \(\{z_0,z_1\}\) alle Zustände durch, ermitteln im NFA die Menge der Nachfolgezustände von \(x\), also \(\delta(z_0,x)\) und \(\delta(z_1,x)\), und vereinigen diese Mengen. Die sich so ergebene Menge ist der Nachfolgezustand im DFA für das Symbol \(x\).

 Wegen \(\delta(z_0, a) = \{z_0, z_1\}\) und \(\delta(z_1, a) = \{z_2\}\) ergibt sich \(\delta'(\{z_0, z_1\},a) = \{z_0, z_1, z_2\}\). Für \(b\) ergibt sich analog \(\delta'(\{z_0, z_1\},b) = \{z_0, z_2\}\).

Wir haben nun also zwei neue Zustände erzeugt und verfahren mit diesen nun wie eben weiter. Für den Zustand \(\{z_0, z_2\}\) ergibt sich wegen \(\delta(z_0, b) = \{z_0\}\) und \(\delta(z_2, b) = \emptyset\) dann \(\delta'(\{z_0, z_2\},b) = \{z_0\}\) und wegen \(\delta(z_0, a) = \{z_0, z_1\}\) und \(\delta(z_2, a) = \emptyset\) dann \(\delta'(\{z_0, z_2\},a) = \{z_0, z_1\}\).

 

Für \(\{z_0, z_1, z_2\}\) ergibt sich wegen \(\delta(z_0, b) = \{z_0\}\), \(\delta(z_1, b) = \{z_2\}\) und \(\delta(z_2, b) = \emptyset\) dann \(\delta'(\{z_0, z_1, z_2\},b) = \{z_0, z_2\}\) und analog für \(\delta'(\{z_0, z_1, z_2\},a) = \{z_0, z_1, z_2\}\).

Wir haben nun für jeden Zustand für jedes Symbol Kanten und sind damit mit der Konstruktion (fast) fertig. Die Endzustände fehlen uns nun noch. Nach der Konstruktion werden all jene Zustände des DFA zu Endzuständen, die mindestens einen Endzustand des NFA enthalten. Dies sind hier gerade \(\{z_0, z_2\}\) und \(\{z_0, z_1, z_2\}\), da nur diese den einzigen Endzustand \(z_2\) des NFA enthalten. Damit ergibt sich letztendlich der rechts abgebildete Automat.

Dies schließt die Konstruktion ab. Wir hätten streng nach der angegebenen Konstruktion noch weitere Zustände konstruieren müssen, die aber für die akzeptierte Sprache nicht von Bedeutung sind, da sie vom Startzustand aus nicht erreicht werden können. Wir kommen auf diesen Unterschied später noch einmal zu sprechen.

 
Damit haben wir gezeigt, dass wir zu jedem NFA einen DFA konstruieren können, der die gleiche Sprache akzeptiert. Da die Menge der Zustände des DFA gerade die Potenzmenge der Zustände des NFA ist, wird diese Konstruktion Potenzautomatenkonstruktion und der entstehende DFA der Potenzautomat (zu dem NFA) genannt.

Man spricht in diesem Fall von der Äquivalenz der beiden Automatenmodelle. Allgemein sagt man, dass, wenn zwei DFAs \(A_1\) und \(A_2\) die gleiche Sprache akzeptieren, wenn also \(L(A_1) = L(A_2)\) gilt, dass dann \(A_1\) und \(A_2\) äquivalent sind. Ebenso spricht man dann auch bei zwei Automaten unterschiedlicher Automatenmodelle davon, dass sie äquivalent sind, wenn sie die gleiche Sprache akzeptieren. Und letztendlich spricht man in dem Fall, dass es so wie hier möglich ist, zu jedem Automaten eines speziellen Modells einen äquivalenten Automaten eines anderen speziellen Modells zu konstruieren, davon, dass die Automatenmodelle äquivalent sind. NFAs und DFAs sind also äquivalente Automatenmodelle oder kürzer: äquivalent.

Zum Abschluss noch der Hinweis auf den Unterschied in der Konstruktion im Beweis und im Vorgehen im Beispiel. In der Konstruktion im Beweis wurde \(Z‘ := 2^Z\) gesetzt. Im Beispiel haben wir nur die initiale Zusammenhangskomponente konstruiert. Letzteres genügt stets, d.h. man könnte die Konstruktion im Beweis so umformulieren, dass man sie algorithmisch formuliert und bei \(z_0 := Z_{start}\) beginnt und dann (so wie im Beispiel) nach und nach weitere, erreichbare Zustände (also insgesamt die initiale Zusammenhangskomponente) generiert. Der Korrektheitsbeweis geht dann ganz genauso. Die Aussagen bleiben also die gleichen, bei der Ausführung oder Implementierung ist die Variante mit der initialen Zusammenhangskomponente aber meist schneller und platzsparender. In der Konstruktion im Beweis wurde hier die eher statische Variante gewählt, um die Potenzmenge deutlich sichtbar zu machen.

Tatsächlich gibt es auch Fälle, in denen alle Zustände der Potenzmenge nötig sind, d.h. es gibt Fälle, in denen der DFA exponentiell mehr Zustände benötigt als der DFA ([/latex]2^{|Z|}[/latex] im Vergleich zu \(|Z|\)). In den meisten Fällen werden zwar nicht alle gebraucht, es gibt aber eben doch Beispiele, wo diese Zahl erreicht wird und tatsächlich auch nötig ist, d.h. die hohe Zahl ist auch keine Schwäche der Konstruktion!

Eine gute Näherung für diesen Fall hat man schon mit dem Automaten, bei dem das drittletzte Symbol ein bestimmter Buchstabe sein muss bzw. mit Verallgemeinerungen davon.

Ein äquivalenter DFA für diese Sprache hat bereits mindestens \(2^{n-1}\) Zustände.

 
Bei einem vollständigen DFA gibt es zu jedem Zustand \(z\), in dem sich der DFA befindet, und jedem Eingabesymbol \(x\), das er in diesem Zustand liest, genau einen Nachfolgezustand \(\delta(z,x) = z‘\). Ist der DFA nicht vollständig, dann gibt es höchstens einen Nachfolgezustand. Man spricht daher davon, dass der Nachfolgezustand beim DFA determiniert ist (darum auch die Bezeichnung als deterministischer endlicher Automat). Ist ein DFA \(A\) nämlich in einem Zustand \(z\), dann gibt es stets nur genau eine Möglichkeit, was bei einem Symbol \(x\) passiert. Entweder passiert der Zustandswechsel zu einem ganz bestimmten Zustand oder der Automat blockiert.

In den späten 1950er Jahren kam die Idee auf, der Übergangsfunktion des DFA mehr Freiheiten einzuräumen. Statt nur einen Nachfolgezustand zu haben, darf der neue Automat nun beim Lesen eines Buchstaben mehrere Nachfolgezustände haben.

Im abgebildeten Automaten gibt es in \(z_0\) zwei Möglichkeiten den Zustand beim Lesen von \(a\) zu wechseln. Die Idee ist, dass nichtdeterministisch ein Nachfolgezustand gewählt wird. Man interpretiert dies so, dass der Automat sowohl in \(z_1\) als auch in \(z_2\) ist und quasi in der Rückschau das bessere ausgewählt wird.

Akzeptiert wird daher, informal ausgedrückt, sobald es mindestens eine Rechnung gibt, die den Automaten vom Start- in einen Endzustand bringt. Endliche Automaten, die wie der abgebildete Automaten mehrere gleichbeschriftete Kanten aus einem Zustand heraus haben, also nichtdeterministisch sind, werden als NFA (nichtdeterministischer endlicher Automat) bezeichnet.

Nichtdeterminismus einzuführen war eine wegweisende Idee, die uns an vielen Stellen in der Informatik begegnet. Hier ist sie insb. deswegen nützlich, weil sie uns oft erlaubt, auf einfache Weise Automaten zu entwerfen, die als DFAs viel komplizierter sind. Will man z.B. einen Automaten für alle Worte, die auf \(1\) enden, so kann man dafür schnell den neben stehend abgebildeten Automaten konstruieren.

 
Der DFA ist in diesem Fall nicht viel komplexer, aber man versuche dies einmal zu verallgemeinern und z.B. einen DFA zu entwerfen, der jene Worte akzeptiert, dessen fünftletzter Buchstabe \(1\) ist. Dies ist ein recht großer und schwer zu lesender DFA, mit Nichtdeterminismus aber sehr schnell konstruiert.

Zudem werden wir Nichtdeterminismus bei späteren Automatenmodellen benötigen und insb. bei der Turingmaschine und der damit zusammenhängenden Komplexitätstheorie wird dieses Konzept unglaublich hilfreich sein. Mit ihm lassen sich einige der ganz großen offenen Fragen der Informatik formulieren.

Definition des NFA

Den nichtdeterministischen endlichen Automaten (kurz: NFA) können wir formal fast wie den DFA einführen. Wir müssen nur bei der Übergangsfunktion etwas anders machen, um mehrere Nachfolgezustände ausdrücken zu können. Dies gelingt indem wir die Zielmenge von \(Z\) zu \(2^Z\) ändern. Damit ist \(\delta(z,x)\) dann eine Menge von Zuständen. In dieser Menge sind dann gerade jene Zustände, die von \(z\) aus mit \(x\) erreichbar sind.

Zusätzlich wollen wir auch eine Menge von Startzuständen zulassen. Dies beschreibt, dass wir auch nach dem Lesen von null Symbolen nichtdeterministisch in mehreren Zuständen sein können, das also bereits der Anfang nichtdeterminiert ist.

Formal können wir dies nun wie folgt exakt ausdrücken.

Die graphische Darstellung ist wie beim DFA.

Alternativ kann statt der Überführungsfunktion \(\delta\) auch mit der Zustandsübergangsrelation $$ K \subseteq Z \times \Sigma \times Z $$ arbeiten. Ein Tupel \((z,x,z‘)\) drückt dann aus, das es von \(z\) eine Kante nach \(z‘\) gibt, die mit \(x\) beschriftet ist. Es ist dann bei einem NFA möglich weitere Kanten mit gleichem Ursprung und gleichem Symbol zu haben, also z.B. zwei Kanten \((z,x,z‘)\) und \((z,x,z“)\).

Beispiel

Im abgebildeten Automaten ist dann \(Z = \{z_0, z_1\}\), \(\Sigma = \{0,1\}\) und \(Z_{end} = \{z_1\}\) wie beim DFA. Da dies ein NFA ist, haben wir aber, obwohl es in diesem Fall wie beim DFA nur ein Startzustand ist, eine Startzustandsmenge, also ist \(Z_{start} = \{z_0\}\).

Die Überführungsfunktion ist durch \(\delta(z_0, 0) = \{z_0\}\) und \(\delta(z_0, 1) = \{z_0, z_1\}\) gegeben. Außerdem kann man \(\delta(z_1, 0) = \delta(z_1, 1) = \emptyset\) setzen.

Als Zustandsübergangsrelation ist \(K\) gegeben durch \(K = \{(z_0,0,z_0), (z_0,1,z_0), (z_0,1,z_1)\}\).

 
Da wir die Überführungsfunktion angepasst haben, müssen wir auch die erweiterte Überführungsfunktion und letztendlich die akzeptierte Sprache anpassen. Für die erweiterte Überführungsfunktion definieren wir folgendes.

Wir werden meistens mit der zweiten Alternative arbeiten. Hier sammeln sich die nichtdeterministisch erreichten Zustände in der Menge im ersten Argument.

Beispiel

Sei der folgende Automat gegeben. Wir haben einen Startzustand und interessieren uns für das Wort \(aba\).

Damit ergibt sich

\(\begin{eqnarray*} \hat{\delta}(\{z_0\}, aba) & = & \hat{\delta}(\{z_0, z_1\}, ba) \\ & = & \hat{\delta}(\{z_0\} \cup \{z_2\}, a) \\ & = & \hat{\delta}(\{z_0, z_2\}, a) \\ & = & \hat{\delta}(\{z_0, z_1\} \cup \emptyset, \lambda) \\ & = & \hat{\delta}(\{z_0, z_1\}, \lambda) \\ & = & \{z_0, z_1\} \end{eqnarray*}\)

Man beachte, wie sich im ersten Argument die Menge der erreichten Zustände sammelt. Um z.B. \(\hat{\delta}(\{z_0, z_1\}, ba) = \hat{\delta}(\{z_0\} \cup \{z_2\}, a)\) zu sehen, muss man die Nachfolgezustände von \(\{z_0, z_1\}\) beim Lesen des nächsten Buchstabens (also von \(b\)) ermitteln. Dazu nimmt man die Menge der Zustände, die von \(z_0\) aus durch \(b\) erreicht werden (also \(\delta(z_0, b) = \{z_0\}\)) und vereinigt diese mit der Menge der Zustande, die von \(z_1\) durch \(b\) aus erreichbar sind (also mit \(\delta(z_1, b) = \{z_2\}\)). Damit ergibt sich obiges.

 
Bevor wir zur akzeptierten Sprache kommen, können wir noch wie beim DFA die Konfiguration, Konfigurationsübergänge, sowie Rechnungen und Erfolgsrechnungen definieren.

Man beachte wie gering die Unterschiede zum DFA sind. Beim DFA wird beim Konfigurationsübergang \(z‘ = \delta(z,x)\) gefordert, hier wird \(z‘ \in \delta(z,x)\) gefordert. Bei der Rechnung wird gefordert, dass \(z_0\) ein Startzustand ist (wie beim DFA auch, aber hier könnte man mehrere zur Auswahl haben).

Man beachte insbesondere aber auch, dass anders als beim DFA hier bei der Konfiguration Informationen verloren gehen! Ein NFA kann sozusagen in mehreren Konfigurationen gleichzeitig sein. Der Sinn hier ist, dass man über bestimmte Rechnungen ähnlich wie beim DFA sprechen will.

Wir können nun die akzeptierte Sprache definieren.

Ein NFA \(A\) akzeptiert also ein Eingabewort \(w\) dann, wenn auf \(w\) eine Erfolgsrechnung existiert, d.h. wenn es eine Rechnung gibt, die in \((z_0, w)\) mit \(z_0 \in Z_{start}\) beginnt und in \((z_e, \lambda)\) mit \(z_e \in Z_{end}\) endet. Die Notation \(\hat{\delta}(Z_{start}, w) \cap Z_{end} \not= \emptyset\) drückt das gleiche aus, nutzt aber die erweiterte Überführungsfunktion.

Beispiel

Betrachten wir noch einmal den folgenden Automaten \(A\).

Wir betrachten das Wort \(w = 011\). Auf diesem Wort hat der Automat drei Rechnungen:

1. \((z_0, 011) \vdash (z_0, 11) \vdash (z_1, 1)\) – blockiert
2. \((z_0, 011) \vdash (z_0, 11) \vdash (z_0, 1) \vdash (z_0, \lambda)\) – lehnt ab
3. \((z_0, 011) \vdash (z_0, 11) \vdash (z_0, 1) \vdash (z_1, \lambda)\) – akzeptiert

Im ersten Fall blockiert der Automat, da es in \(z_1\) keine \(1\)-Kante gibt. Im zweiten Fall lehnt der Automat das Wort ab, da die Rechnung in \(z_0\) endet und dies kein Endzustand ist.

Im dritten Fall ist das Wort zu Ende gelesen und der Automat in einem Endzustand, also wird das Wort akzeptiert. Wegen dieses dritten Falles wird das Wort auch ganz allgemein akzeptiert, soll heißen: es gilt \(001 \in L(A)\).

Man mache sich noch einmal klar, dass ein NFA ein Wort akzeptiert, sobald es irgendeine Rechnung gibt, die ihn von einem Start- zu einem Endzustand bringt. Ein NFA muss, um ein Wort zu akzeptieren, dieses wie ein DFA zu Ende gelesen haben und er muss dann in einem Endzustand sein. Er kann aber auf einem Wort mehrere Rechnungen haben und es genügt, wenn mindestens eine davon eine Erfolgsrechnung ist.

Wie gehen wir nun vor, wenn wir eine Sprache \(M\) haben und einen Automaten \(A\) mit \(L(A) = M\) konstruieren wollen? Dieser Entwurf eines Automaten erfordert von uns Kreativität und lässt sich nicht automatisieren, d.h. es gibt kein Rezept dafür, dem wir folgen können, um am Ende den Automaten \(A\) zu haben. Es gibt allerdings Techniken, die man erlernen kann und je nach \(M\) vielleicht anwenden kann. Wir wollen nachfolgend zwei solcher Techniken erläutern und jeweils anhand eines Beispiels illustrieren.

Technik 1: Mit dem Speicher arbeiten

Bei der ersten Technik fragen wir uns, was für Informationen wir speichern wollen und wie wir dies mit den Zuständen machen können. Der endliche Automat hat ja eine endliche Menge von Zuständen und diese endliche Menge kann genutzt werden, um endliche viele Informationen zu speichern. Z.B. könnte man sich für das zuletzt gelesene Symbol der Menge \(\Sigma = \{0,1\}\) interessieren und dafür zwei Zustände \(z_0\) und \(z_1\) anlegen. In \(z_0\) wechselt man dann, wenn man eine \(0\) liest, in \(z_1\), wenn man eine \(1\) liest. Im Index des Zustands merkt man sich also das zu letzt gelesene Symbol. Wichtig hierbei ist, dass man sich nur endlich viele Informationen merken kann. Man muss also aus der gegebenen Sprache \(M\) wichtige Eigenschaften herleiten, die man in den Zuständen speichert und die einem dann tatsächlich bei der Akzeptierung der Worte aus \(M\) nützen. Ferner muss es auch möglich sein, die Informationen zu aktualisieren. Oben geschah dies ganz einfach stets beim Lesen des nächsten Symbols.

Wir wollen diese Technik an einem Beispiel verdeutlichen. Sei
$$ M := \{ w \in \{0,1\}^* \mid \text{ \(|w|_0\) ist gerade und \(|w|_1\) ist ungerade} \} $$ In \(M\) sind also jene Worte aus \(0\)en und \(1\)en, die eine gerade Anzahl an \(0\)en und eine ungerade Anzahl an \(1\) en enthalten. Zum Beispiel ist also \(01110 \in M\) (zwei \(0\)en und drei \(1\)en), nicht aber \(0101\) (die Anzahl der \(0\)en ist zwar gerade, die der \(1\)en aber auch).

Wie konstruieren wir hierzu nun einen DFA? Dazu muss man sich überlegen, welche speziellen Eigenschaften ein Wort aus \(M\) hat und ob man sich diese Eigenschaften mit endliche vielen Informationen merken kann. Bevor unten ein Lösungsvorschlag kommt, kann man an dieser Stelle einmal selbst ausprobieren, ob man auf eine Lösung kommt.

Eine Beispiellösung

Ein Wort \(w \in M\) hat die Eigenschaft gerade viele \(0\)en und ungerade viele \(1\)en zu enthalten. Wenn wir nun die Anzahl der \(0\)en und der \(1\)en zählen und diese Information im Zustand speichern wollen, dann brauchen wir unendlich viele Zustände, da wir ja Hundert oder auch Tausend oder auch Zehntausend \(0\)en lesen können. Dieser Ansatz geht also nicht. Wir brauchen aber auch gar nicht die genaue Anzahl der \(0\)en und \(1\)en. Es genügt ja zu wissen, ob wir bis zu einem bestimmten Zeitpunkt gerade oder ungerade viele \(0\)en gesehen haben. Dies sind zwei Informationen (gerade oder ungerade) für zwei Symbole ([/latex]0[/latex] und \(1\)), also brauchen wir insgesamt nur vier Zustände für die vier Fälle gerade viele \(0\)en und gerade viele \(1\)en, gerade viele \(0\)en und ungerade viele \(1\)en usw. Zudem können wir die gespeicherten Informationen leicht aktualisieren, wenn der Automat eine \(0\) oder eine \(1\) liest.

Um dies im Detail auszuführen nehmen wir als Zustände \(z_{gg}, z_{ug}, z_{gu}\) und \(z_{uu}\). Ein \(u\) im Index steht dabei für ungerade, ein \(g\) für gerade. Das erste Symbol steht für die \(0\)en, das zweite für die \(1\)en. Der Zustand \(z_{ug}\) soll also erreicht werden, wenn wir ungerade viele \(0\)en und gerade viele \(1\)en gelesen haben. Als Startzustand macht dann \(z_{gg}\) Sinn, da wir null gelesene \(0\)en und null gelesene \(1\)en als gerade viele \(0\)en und \(1\)en ansehen wollen. Der Endzustand ist mit Blick auf die Menge \(M\) dann \(z_{gu}\). Damit haben wir als Zustandsübergangsdiagramm des Automaten \(A\) bisher den gezeigten Automaten.

 

Wenn wir nun in \(z_{gg}\) sind und eine \(0\) lesen, dann ändert sich die gespeicherte Information, dass wir gerade viele \(0\)en gelesen haben, denn es kommt ja eine dazu und damit sind es nun ungerade viele. Die gespeicherte Information zu den \(1\)en hingegen ändert sich nicht. Wir machen also eine \(0\)-Kante in den Zustand \(z_{ug}\), da wir nun ungerade viele \(0\)en und weiterhin gerade viele \(1\)en gelesen haben. Ebenso machen wir eine \(1\)-Kante von \(z_{gg}\) nach \(z_{gu}\). Dies ergibt als Automat nun folgendes Bild.

 

Man überlegt sich dann schnell, dass für die eben eingezeichneten Kanten auch Kanten mit der gleichen Beschriftung zurück nötig sind, da gerade wieder die gleiche gespeicherte Information geändert werden muss. Ebenso kann man sich für die verbleibenden Zustände und Symbole die Kanten überlegen. Ist man z.B. in \(z_{uu}\), so hat man ungerade viele \(0\)en und \(1\)en gelesen und ein Lesen von \(0\) führt dann in \(z_{gu}\), da man dann gerade viele \(0\)en und weiterhin ungerade viele \(1\)en gelesen hat. Insgesamt ergibt sich damit der abgebildete Automat.

 

Wir sind mit der Konstruktion fertig, da wir einen Startzustand haben, eine Endzustandmenge und für jedes Symbol Kanten aus jedem Zustand heraus (der Automat ist also sogar vollständig). Es ist nun aber wie im vorherigen Abschnitt zunächst nur eine Behauptung, dass \(L(A) = M\) tatsächlich gilt. Dies ist nun noch zu beweisen! Dazu kann man sich zuerst überlegen, dass für jeden Zustand und alle Kanten gilt, dass die Informationen richtig neu gesetzt werden. Wenn man also in einem Zustand \(z_{xy}\) ist und mit einer \(0\)-Kante den Zustand \(z_{x'y}\) erreicht bzw. mit einer \(1\)-Kante den Zustand \(z_{xy'}\), dann wird \(x\) richtig in \(x'\) bzw. \(y\) richtig in \(y'\) geändert. Exemplarisch haben wir das bereits oben für einige argumentiert. Man kann am Zustandsdiagramm sehen, dass dies tatsächlich für alle Zustände und alle Kanten gilt. Dies erlaubt gleich die Formulierung, dass bestimmte Dinge "nach Konstruktion" gelten. Wir zeigen nun \(L(A) = M\).

1. Sei \(w \in M\), dann kann \(w\) nach Konstruktion (der Automat ist vollständig) zu Ende gelesen werden. Nach Konstruktion der Zustände und der Zustandsübergänge (s.o.) enden wir dann in \(z_{gu}\) (da \(w\) eine gerade Anzahl von \(0\)en und eine ungerade Anzahl von \(1\)en enthält) und akzeptieren. Also ist auch \(w \in L(A)\).
 
2. Sei \(w \in L(A)\). Da \(w\) akzeptiert wird, muss \(A\) in \(z_{gu}\) enden. Dies ist aber nach Konstruktion (s.o.) gleichbedeutend damit, dass \(w\) gerade viele \(0\)en und ungerade viele \(1\)en enthält. Damit gilt auch \(w \in M\).

Die Formulierung "nach Konstruktion" macht hier Sinn, da wir oben die Idee sauber beschrieben haben und für alle Zustände und Kanten erklären können was passiert. Zudem ist der Automat hinreichend klein und übersichtlich, so dass man dies hier so akzeptieren kann. Noch sauberer gelingt der Beweis mit einer vollständigen Induktion über die Wortlänge. Hier wird dann ebenfalls oben ausgeführtes zu den Zuständen und den Zustandsübergängen benutzt. Man kann aber besser argumentieren, warum man z.B. bei der ersten Beweisrichtung tatsächlich in \(z_{gu}\) landet. Diese Stelle wäre oben noch angreifbar.

Wir beweisen \(L(A) = M\) noch einmal mit Induktion über die Wortlänge. Das schwierige ist dann insb. eine gute Induktionsbehauptung aufzustellen.

1. Sei \(w = w_1 \ldots w_n \in \{0,1\}^*\) (mit \(w_1, \ldots, w_n \in \{0,1\}\)). Wir zeigen mittels Induktion über die Wortlänge \(n\): \(w\) kann von \(A\) gelesen werden und \(A\) endet in \(z_{gg}\), wenn \(|w|_0\) und \(|w|_1\) gerade sind, in \(z_{gu}\), wenn \(|w|_0\) gerade und \(|w|_1\) ungerade ist, in \(z_{ug}\), wenn \(|w|_0\) ungerade und \(|w|_1\) gerade ist und in \(z_{uu}\), wenn \(|w|_0\) und \(|w|_1\) ungerade sind.

   Induktionsanfang: Sei \(n = 0\), dann ist \(w = \lambda\), \(|w|_0\) und \(|w|_1\) sind gerade und \(A\) kann \(w\) lesen und endet in \(z_{gg}\) wie gewünscht.

   Induktionsannahme: Die Induktionsbehauptung gelte für ein \(n \geq 0\)

   .

   

    

   Induktionsschritt: Sei nun \(w = w_1 \ldots w_n w_{n+1}\) ein Wort der Länge \(n+1\). Wir wenden auf \(w' := w_1 \ldots w_n\) die Induktionsannahme an. \(A\) kann \(w'\) also lesen und endet in einem seiner vier Zustände, je nachdem, ob \(|w'|_0\) und \(|w'|_1\) gerade oder ungerade sind. Wir machen eine Fallunterscheidung. Angenommen \(w'\) hat eine gerade Anzahl von \(0\)en und \(1\)en und angenommen \(w_{n+1}\) ist eine \(0\), dann ist \(|w|_0\) ungerade ([/latex]|w'|_0[/latex] haben wir als gerade angenommen und \(w_{n+1}\) als \(0\), damit ist \(|w|_0\) ungerade) und \(|w|_1\) gerade.

   Wir müssen nun zeigen, dass \(w\) von \(A\) gelesen werden kann und dass \(A\) nach Lesen von \(w\) in \(z_{ug}\) ist. Nach der Induktionsannahme und da \(|w'|_0\) und \(|w'|_1\) gerade sind, kann \(A\) das Teilwort \(w'\) lesen und ist nach Lesen von \(w'\) in \(z_{gg}\). Nach Konstruktion überführt \(w_{n+1} = 0\) dann \(A\) nach \(z_{ug}\). Damit haben wir das Gewünschte für diesen Fall bereits gezeigt.

   Analog behandelt man den Fall, dass \(w_{n+1}\) eine \(1\) ist und dann ganz analog die Fälle, dass \(A\) nach Lesen von \(w'\) in einem der anderen drei Zustände ist. Insgesamt sind hier also acht Fälle zu behandeln (die vier Zustände, in denen \(A\) nach Lesen von \(w'\) ist sowie dann jeweils \(w_{n+1} = 0\) oder \(w_{n+1} = 1\)).

   Damit haben wir die Induktionsbehauptung gezeigt. Sei nun \(w \in M \subseteq \{0,1\}^*\). Dann wissen wir, dass \(|w|_0\) gerade und \(|w|_1\) ungerade ist. Nach dem eben bewiesen überführt uns \(w\) also in \(z_{gu}\) und da dies ein Endzustand ist, gilt \(w \in L(A)\).

   Dies sieht alles sehr ähnlich zu obigem aus. Die Konstruktionsidee findet sich im Induktionsschritt wieder. Insgesamt ist der Beweis so aber sauberer als der oben zuerst geführte. In diesem kleinen Beispiel hätte der oben zuerst geführte aber auch genügt. Der Leser muss sich dann aber an der Stelle "Nach Konstruktion der Zustände und der Zustandsübergänge (s.o.) enden wir dann in \(z_{gu}\)"selbst davon überzeugen können, dass die Aussage stimmt. Das ist bei diesem kleinen Beispiel noch recht eingängig. Mit einer Induktion aber stichhaltiger gezeigt.

 
2. Sei \(w \in L(A)\). Wir wollen \(w \in M\) zeigen. Betrachten wir noch einmal obige Induktionsbehauptung, dann haben wir dort wenn-dann-Formulierungen der Art \emph{wenn \(|w|_0\) und \(|w|_1\) gerade sind, dann endet \(A\) in \(z_{gg}\)}. Da es bezüglich gerader und ungerader Anzahl der \(0\)en und \(1\)en nur die vier Fälle für Worte \(w \in \{0,1\}^*\) gibt, sind dies sogar genau-dann-wenn-Beziehungen, d.h. wir können aus obigen sofort auch schlussfolgern, dass z.B. \(|w|_0\) und \(|w|_1\) gerade sind, wenn \(A\) in \(z_{gg}\) endet. (Angenommen \(|w|_0\) und \(|w|_1\) wären nicht beide gerade, dann würde aus der oben bewiesene Induktionsbehauptung folgen, dass \(A\) nicht in \(z_{gg}\), sondern in einem der anderen Zustände endet. Wir sind ja aber gerade davon ausgegangen, dass wir in \(z_{gg}\) enden und hätten hier einen Widerspruch.) Mit dieser Überlegung folgt der Beweis nun ganz schnell. Sei \(w \in L(A)\), dann enden wir in \(z_{gu}\), da dies der einzige Endzustand ist. Dann aber folgt aus dem eben beschriebenen sofort, dass \(|w|_0\) gerade und \(|w|_1\) ungerade ist und damit \(w \in M\) gilt. (Diese Richtung erscheint deswegen so kurz, weil wir im Grunde genommen oben bei der Induktionsbehauptung auch "genau dann, wenn"-Beziehungen gezeigt haben und daher die dortige Aussage hier benutzen können.)

Damit sind wir mit diesem Beispiel fertig.

 
Wir wollen noch anmerken, dass bei dieser Technik bisweilen ein Teil konstruiert wird, der dann gar nicht benötigt wird. Dies kann passieren, wenn man zunächst Speicherinhalte berücksichtig, von denen man später bemerkt, dass man sie gar nicht braucht, weil sie (doch) nicht entstehen können. Dies ist aber nicht weiter tragisch, man würde sich dann einfach im Nachhinein auf die initiale Zusammenhangskomponente (also jenen Teil des Automaten, der vom Startzustand aus erreichbar ist) einschränken.

Technik 2: On-the-fly-Entwurf

Die zweite Technik, die wir kennenlernen wollen ist eine „on-the-fly“-Technik. Man fängt hier mit dem Startzustand an und überlegt sich dann für jedes Eingabesymbol \(x \in \Sigma\), ob einem dieses weitere Informationen bringt, die man speichern will oder nicht. Der so entstehende Automat ist stets initial zusammenhängend und vollständig. Man muss bei der Konstruktion aber darauf achten, dass man irgendwann zu Zuständen zurück kommt, die man bereits generiert hatte, sonst generiert man unendlich viele Zustände.

Wir wollen diese Technik wieder an einem kleinen Beispiel demonstrieren. Sei $$M := \{0,1\}^* \{1\} = \{w \in \Sigma^* \mid \exists v \in \Sigma^*: w = v1\}$$ In \(M\) sind also jene Worte aus \(0\)en und \(1\)en, die auf \(1\) enden. Beispielsweise ist \(0101\) (letztes Symbol ist \(1\)) enthalten, nicht aber \(1010\) (letztes Symbol ist \(0\), nicht \(1\)).

Wir könnten mit der ersten Konstruktionsmethode hierzu einen Automaten bauen, indem wir uns im Speicher merken, was das zuletzt gelesene Symbol ist. Dazu brauchen wir nur zwei Zustände, den das zuletzt gelesene Symbol ist entweder \(0\) oder \(1\). Wir wollen aber nachfolgend die On-the-fly-Technik illustrieren. Man kann trotzdem einmal probieren zunächst selbst einen Automaten zu bauen und seine Richtigkeit zu beweisen, bevor man weiter liest.

Eine Beispiellösung

Wir starten mit einem Startzustand (denn jeder DFA hat einen Startzustand) und fragen uns nun für jedes Symbol aus \(\Sigma\), was wir mit diesem Symbol anstellen können.

 

Bei einer \(0\) wissen wir nicht, ob das letzte Symbol eine \(1\) ist (vielleicht haben wir sogar gerade das letzte Symbol gelesen). Auf jeden Fall wollen wir also nicht akzeptieren. Wir könnten nun einen neuen Zustand erstellen und eine \(0\)-Kante dorthin machen. Bei genauerer Betrachtung merkt man aber, dass dieser Zustand im Vergleich zu \(z_0\) keinen Mehrwert hat. Wir wissen im Grunde genauso viel wie vorher. Daher machen wir besser eine \(0\)-Schleife an \(z_0\).

 

Bei einer \(1\) hingegen müssen wir den Zustand wechseln. Dies könnte ja das letzte Symbol des Wortes sein und dann wollen wir akzeptieren. Wir machen uns also einen neuen Zustand und lassen dort eine \(1\)-Kante von \(z_0\) hinführen. Dies muss zudem ein Endzustand sein, denn diese \(1\) könnte ja das letzte Symbol des Wortes sein und dann wollen wir akzeptieren.

 

Mit dem Zustand \(z_0\) sind wir nun fertig, denn wir haben für jedes Symbol eine Kante. Wir haben allerdings einen neuen Zustand \(z_1\) erzeugt und müssen uns nun fragen, was hier für die einzelnen Symbole von \(\Sigma\) passiert.

Wenn wir in \(z_1\) sind und eine \(1\) lesen, dann ist weiterhin das letzte gelesene Symbol eine \(1\) und wenn dies sogar das letzte Symbol des Wortes ist, wollen wir akzeptieren. Wir verbleiben also in \(z_1\). Wichtig hier ist wieder zu erkennen, dass es nicht nötig ist, einen neuen Zustand einzuführen, sondern dass wir auch nach Lesen weiterer \(1\)en in \(z_1\) verbleiben können, da wir hier genau die Informationen haben, die wir brauchen.

Lesen wir aber hingegen eine \(0\), so müssen wir \(z_1\) verlassen, denn nun ist das letzte gelesene Symbol keine \(1\) mehr und wenn das Wort mit dieser \(0\) endet, dann wollen wir ganz bestimmt nicht akzeptieren. Wir könnten nun einen neuen Zustand \(z_2\) machen und dort die \(0\)-Kante von \(z_1\) hinführen. Dann hätten wir einen weiteren Zustand und müssten uns wieder fragen, was hier bei einer \(0\) oder bei einer \(1\) passiert. Bemerkt man aber an dieser Stelle, dass man wieder die gleichen Informationen hat wie in \(z_0\), so kann man dorthin wechseln und spart sich dies. Der Automat ist dann fertig, da man für alle Zustände Kanten für alle Symbole hat. Der Automat ist also vollständig.

 

Wie immer muss nun aber noch \(L(A) = M\) bewiesen werden. Dies geht allerdings hier deutlich einfacher als in dem vorherigen Beispiel. Man beachte, dass der Automat vollständig ist (also jedes Wort \(w \in \{0,1\}^*\) lesen kann) und dass jede \(1\)-Kante nach \(z_1\) führt.

1. Sei \(w = v1 \in M\) mit \(v \in \{0,1\}^*\). Da der Automat vollständig ist, können \(v\) und \(w\) auf jeden Fall ganz gelesen werden. Da \(w\) auf \(1\) endet, muss der Automat mit dieser letzten \(1\) nach Konstruktion (jeder Zustand hat eine \(1\)-Kante nach \(z_1\)) in den Zustand \(z_1\) wechseln – oder anders: egal wo wir nach Lesen von \(v\) sind, die folgende \(1\) führt uns nach \(z_1\). Mit \(z_1 \in Z_{end}\) folgt \(w \in L(A)\).
 
2. Sei \(w \in L(A)\). Dann muss nach Konstruktion das Wort auf \(1\) enden, da \(z_1\) der einzige Endzustand ist und alle Kanten nach \(z_1\) mit \(1\) beschriftet sind. Dann ist aber sofort auch \(w \in M\).

Damit sind wir auch mit diesem Beispiel fertig.

 
Wir betonen noch einmal, dass es bei dieser Konstruktionsmethode kritisch ist irgendwann zu merken, wann bereits vorhandene Zustände benutzt werden können – und im besten Fall auch, wofür sie stehen; bspw. kann man oben \(z_x\) mit „letztes gelesenes Symbol ist \(x\)“ identifizieren (\(x \in \{0,1\}\)). Ansonsten konstruiert man immer weiter Zustände und der Automat wird nicht endlich.

Ein kompliziertes Beispiel

Wir wollen zum Abschluss dieses Abschnittes noch ein komplizierteres Beispiel betrachten. Bei einigen der oben bisher betrachteten Mengen und Automaten mag der ein oder andere denken, dass man die Lösung doch gleich sehe und warum man dann so umständlich argumentieren müsse? Die bisherigen Beispiele sollten das Vorgehen einüben und waren deswegen nicht zu kompliziert gewählt, damit man nicht sofort von umständlichen Argumentationen überwältigt wird. So konnte man sich auf das Vorgehen an sich konzentrieren und die Argumentationen blieben vergleichsweise übersichtlich. Damit wir aber noch einmal sehen können, dass die Argumente durchaus komplexer werden können, betrachten wir nun noch ein komplizierteres Beispiel.

Sei zunächst $$ \Sigma = \{ \begin{bmatrix} x \\ y \\ z \end{bmatrix} \mid x,y,z \in \{0,1\} \}. $$ Ein Symbol aus \(\Sigma\) ist also eine Art Vektor mit drei Elementen oder für uns nachfolgend besser mit drei Zeilen. Ein Wort aus \(\Sigma^*\) kann dann nämlich als drei Zeilen mit \(0\)en und \(1\)en gesehen werden. Im Wort
$$ \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}
\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}
\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}
\begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} $$
ist bspw. die erste Zeile \(0 1 1 0\), die zweite Zeile \(0 1 1 1\) und die dritte Zeile \(1 1 0 1\). Wir interpretieren nun jede Zeile als Binärzahl und betrachten die Sprache $$ Sum = \{ w \in \Sigma^* \mid \text{ die unterste Zeile ist Summe der oberen Zeilen} \} $$ In dem oben notierten Wort aus vier Symbolen ist dies der Fall, es wäre also in \(Sum\). Wir fragen nun: Ist \(Sum\) regulär?

Die Idee und der Automat

Mit der Idee von eben, \(Sum^R\) zu betrachten gelangen wir weiter. Wir lesen nun quasi eine binäre Addition von rechts nach links und können an jeder Stelle prüfen, ob richtig gerechnet wird. Falls dabei ein Übertrag auftritt, dann merken wir uns diesen im Zustand. Da es nur die Möglichkeit für einen Übertrag von \(0\) oder von \(1\) gibt, sind dies nur zwei Informationen und wir kommen mit endlich vielen Zuständen aus! Wir beginnen in einem Startzustand \(z_0\), mit dem wir gleichzeitig Übertrag \(0\) symbolisieren wollen. Kommt nun als erster Buchstabe ein Vektor wie \((0,0,0)\) oder \((1,0,1)\) (für die bessere Lesbarkeit schreiben wir die Vektoren hier als Zeilen; das erste Element im Vektor entspricht der ersten Zeile, das zweite Element der zweiten Zeile und das dritte Element der dritten Zeile), so können wir in \(z_0\) bleiben, denn in beiden Fällen ist die dritte Zeile (bzw. das dritte Element, in der Schreibweise als Tupel von eben) Summe der ersten beiden Zeilen (der ersten beiden Elemente) und es gibt keinen Übertrag. Entsprechendes gilt für \((0,1,1)\).

Bei \((1,1,0)\) hingegen stimmt zwar die Addition, wir haben aber einen Übertrag, d.h. wir müssen den Zustand wechseln. Hierfür erstellen wir einen neuen Zustand \(z_1\), in dem wir uns merken, dass wir Übertrag \(1\) haben. Alle anderen Symbole wie z.B. \((0,0,1)\) oder \((1,1,1)\) entsprechen Fehlern in der Rechnung, denn wenn wir keinen Übertrag haben (wir sind ja noch in \(z_0\)), dann ist \(0 + 0\) nicht \(1\) und \(1+1\) auch nicht. Analog für die anderen beiden fehlenden Symbole. Diese vier Symbole führen also in einen neuen (Fehler-)Zustand. Der Fehlerzustand hat zudem für jedes \(x \in \Sigma\) eine Kante zu sich selbst. Hier kann das Wort also zu Ende gelesen werden, wird aber nicht akzeptiert.

In \(z_1\) haben wir nun Übertrag \(1\) und wir gehen wieder alle Symbole durch und prüfen, ob die Rechnung an dieser Stelle stimmt. Dabei beachten wir aber den Übertrag von \(1\). So bleiben wir z.B. mit \((1,0,0)\) in \(z_1\), denn \(1 + 0\) ist zwar \(1\), aber wenn nun noch der Übertrag \(1\) hinzukommt, so haben wir richtigerweise in der dritten Zeile eine \(0\) und merken uns wieder den Übertrag von \(1\) (in \(z_1\)). Analog für \((0,1,0)\) und \((1,1,1)\). Das Symbol \((0,0,1)\) führt nun zurück zu \(z_0\), denn \(0+0\) plus den Übertrag ergibt \(1\), aber wir haben nun keinen Übertrag mehr, den wir uns merken müssten und gehen zurück nach \(z_0\). Die anderen vier Symbole führen wieder in den Fehlerzustand, da hier ein Fehler in der Rechnung aufgetreten ist. Zuletzt wählen wir noch \(z_0\) als Endzustand, da wir nur Worte akzeptieren wollen, die korrekte Rechnungen sind, bei denen also auch kein Übertrag mehr besteht. Dies ergibt den abgebildeten Automaten. Dieser ist schon recht kompliziert und seine Korrektheit ist nicht sofort ersichtlich. Daher ist hier ein nachvollziehbarer Beweis von \(L(A) = Sum^R\) dringend nötig.

 
Dieses kompliziertere Beispiel schließt diesen Abschnitt ab. Man beachte, wie hier wieder
eine Induktion über die Wortlänge als Beweistechnik eingesetzt wurde.

 
Üblicherweise wollen wir nun zu einer Sprache \(M\), die uns interessiert, einen DFA \(A\) konstruieren, der diese Sprache akzeptiert, d.h. einen mit \(L(A) = M\). Eine Sprache, die uns interessieren könnte, könnte z.B. die Menge aller Wörter sein, die mit \(a\) beginnen oder die Menge aller Wörter, die das Wort \(aa\) als Teilwort enthalten.

 
Der zur Menge \(M\) konstruierte Automat \(A\) soll genau die Wörter in \(M\) akzeptieren (nicht mehr, nicht weniger), denn sonst gilt nicht \(L(A) = M\). Dies ist aber wichtig, denn hat man nur \(L(A) \subset M\), dann akzeptiert der Automat nicht jedes Wort aus \(M\) und ist daher fehlerhaft. Hat man nur \(M \subset L(A)\), dann akzeptiert der Automat weitere Worte, die er eigentlich nicht akzeptieren soll, was ebenfalls fehlerhaft ist.

 
In diesem Abschnitt wollen wir uns zwei Konstruktionsmethoden für DFAs ansehen und uns mit den Beweisen von \(L(A) = M\) beschäftigen, denn auch wenn man einen Automaten \(A\) konstruiert hat, dann ist \(L(A) = M\) zunächst nur eine Behauptung oder Vermutung. Diese ist dann noch zu beweisen.

Der hier aus didaktischen Gründen auftreten Fall, zu einem gegebenen Automaten \(A\) die Menge \(M\) mit \(L(A) = M\) zu ermitteln (und dies zu beweisen), tritt in Anwendungen kaum auf. Dies wäre ungefähr so als müsste man zu unkommentierten Code, dessen Bedeutung ermitteln. Zum Erlernen der Funktionsweise von Automaten ist dies aber ein ganz praktisches Vorgehen, daher tritt dies hier und in der Literatur meist ein paar Mal auf.

Ein erstes Beispiel

Betrachten wir als erstes Beispiel den abgebildeten Automaten.

Nachdem man den Automaten etwas untersucht hat, kommt man nach einigem Nachdenken und Ausprobieren einzelner Worte zu der Vermutung, dass die akzeptierte Sprache gerade \(\{a\} \cdot \{b\}^* \cdot \{a\}\) sein könnte. Zur Erleichterung der Notation setzen wir \(M := \{a\} \cdot \{b\}^* \cdot \{a\}\) und nennen den Automaten \(A\). Unsere Vermutung oder Behauptung ist nun also, dass \(L(A) = M\) gilt.

 
Einigen ist der Beweis oben bestimmt zu länglich. Wir waren dort absichtlich ganz besonders ausführlich. Der Beweis geht aber auch viel kürzer.

 
Nachfolgend werden die Beweise in ähnlichen Beispielen an vielen Stellen deutlich kürzer ausfallen. Es ist aber eine gute Übung sich zu Anfang jedes Argument sehr kleinschrittig zu überlegen und aufzuschreiben und sich auch später bei schnelleren Argumentationen, genau zu überlegen, ob die Schritte nachvollziehbar sind (sowohl wenn man selbst schneller vorgeht als auch wenn man schneller voranschreitende Beweise liest).

Noch ein Beispiel

Wir wollen als weiteres Beispiel den folgenden Automaten betrachten und diesmal mit einer Annahme beginnen, die sich während des Beweises als falsch herausstellt. Das Beispiel ist zwar wieder so klein, dass man die richtige Sprache gleich erkennen kann, es geht hier aber darum, die Vorgehensweise einzuüben und dafür bieten sich kleinere Beispiele an. Außerdem werden wir hier eine Beweisidee kennenlernen, die an verschiedenen Stellen nützlich sein kann. Später folgt dann auch noch ein größeres und komplizierteres Beispiel.

Angenommen wir vermuten nun, dass die von diesem Automaten akzeptierte Sprache die Menge \(M := \{0,1\}^* \cdot \{1\} \cdot \{0,1\}^*\) ist. Wir vermuten also, dass \[ L(A) = \{0,1\}^* \cdot \{1\} \cdot \{0,1\}^* = M\] gilt.

Warum machen wir das?

Tatsächlich ist die akzeptierte Sprache natürlich \(\{0\}^* \cdot \{1\}\) und wir haben beim Aufstellen von \(M\) einen Fehler gemacht. Dieses negative Beispiel soll noch einmal illustrieren, wie wir beim Beweis von \(L(A) = M\) vorgehen und das Fehler beim Aufstellen von \(M\) passieren können, die dann beim Beweisen (hoffentlich) auffallen und korrigiert werden können.

 
Wir gehen so vor wie eben und versuchen, die zwei Teilmengenbeziehungen zu zeigen.
 

 
Aus dem Beweis(versuch) von eben ergibt sich auch gleich ein Gegenbeispiel. Das Wort \(010\) kann z.B. von dem Automaten nicht akzeptiert werden, ist aber in \(M\).

Im besten Fall kann man nach solch einem Beweisversuch auf eine bessere Idee für \(M\) kommen und einen neuen Beweisversuch starten. Wir vermuten nun, dass \(M‘ := \{0\}^* \cdot \{1\}\) die akzeptierte Sprache ist, unsere Vermutung ist nun also $$ L(A) = \{0\}^* \cdot \{1\} = M‘. $$
 

Nun gelingt der Beweis und wir haben \(L(A) = M‘\) gezeigt.

 
Dies schließt unsere Betrachtungen zu Automaten und ihren akzeptierten Sprachen ab. Im nächsten Abschnitt geht es dann um zwei Konstruktionsmethoden, um einen Automaten zu einer Sprache \(M\) zu konstruieren.

 
Nach den Vorarbeiten des letzten Abschnittes sind wir nun in der Lage den deterministischen endlichen Automaten formal einzuführen. Wir erinnern noch einmal an die Überlegung, die wir in der Einleitung angestellt haben. Wichtig für den endlichen Automaten war, dass

• wir ein System mit einer endlichen Anzahl von Zuständen haben,
• von denen einer als Startzustand und
• eine beliebige Teilmenge als Endzustände hervorgehoben sind,
• dass Zustandsübergänge möglich sind und
• dass das System sich stets in genau einem Zustand befindet.

Formal können wir dies wie folgt exakt beschreiben.

Mit den Zustandsmenge \(Z = \{z_0, z_1\}\), dem Startzustand \(z_0\), der Endzustandsmenge \(Z_{end} = \{z_1\}\) und der Überführungsfunktion \(\delta\), die durch \(\delta(z_0, 0) = z_0\), \(\delta(z_0, 1) = z_1\) und \(\delta(z_1, 0) = z_1\) gegeben ist. (Man beachte, dass \(\delta(z_1, 1)\) nicht definiert ist. Die Funktion \(\delta\) muss nicht total sein und wir werden gleich sagen, dass der Automat in solchen Fällen blockiert.) Sofern nicht anders erwähnt ist das Eingabealphabet \(\Sigma\) die Menge der Symbole, die als Kantenbeschriftungen benutzt werden. Im abgebildeten Beispiel wäre also \(\Sigma = \{0,1\}\). Eine solche graphische Darstellung eines DFA \(A\) wird als Zustandsübergangsdiagramm von \(A\) bezeichnet.

Dies beschreibt nun zunächst nur die Struktur eines DFA. Um auch seine Dynamik, d.h. sein Verhalten beschreiben zu können. Machen wir uns zunächst noch einmal informal klar, wie ein DFA arbeiten soll. Die Eingabe für einen DFA \(A = (Z, \Sigma, \delta, z_0, Z_{end})\) ist ein Wort aus \(\Sigma^*\). Sei dieses Wort mit \(w\) bezeichnet (also \(w \in \Sigma^*\) ist \(\Sigma = \{a,b\}\), so könnte \(w\) z.B. \(abbb\) sein). \(A\) arbeitet dann wie folgt:

1. \(A\) beginnt im Startzustand \(z_0\).
2. Beginnt \(w\) mit dem Symbol \(x \in \Sigma\),
3. so wird der Nachfolgezustand nun durch \(\delta(z_0, x)\) bestimmt.
4. Dies wird dann in dem nun aktuellen Zustand und mit dem Restwort fortgeführt (ist \(A\) also z.B. nun in \(z\) und ist der nächste Buchstabe ein \(y\), so ist der Nachfolgezustand \(\delta(z,y)\) usw.)
5. Das Wort \(w\) wird akzeptiert, wenn
   • \(w\) bis zum Ende gelesen werden kann und
   • der Automat dann in einem Endzustand ist.

Das Wort wird nicht akzeptiert, wenn der Automat entweder nach Lesen des Wortes nicht in einem Endzustand ist oder wenn das Wort nicht zu Ende gelesen werden kann. Letzteres passiert, wenn er in einem Zustand \(z\) ist und das Symbol \(x\) als nächstes gelesen werden soll, es aber keinen Nachfolgezustand gibt, d.h. wenn \(\delta(z,x)\) nicht definiert ist (oder im Diagramm: wenn es keine Kante aus \(z\) heraus gibt, die mit \(x\) beschriftet ist).

Betrachten wir das Beispiel aus Abbildung 2.4. Der Startzustand ist \(z_0\) (markiert durch den eingehenden Pfeil), der einzige Endzustand ist \(z_2\) (markiert durch die doppelten Kreise). Die Werte von \(\delta\) werden durch die Kantenrichtungen und Kantenbeschriftungen ausgedrückt, bspw. ist \(\delta(z_0, a) = z_1\) und \(\delta(z_0, b)\) nicht definiert (beginnt ein Wort also mit \(b\) kann der Automat dieses Wort nicht akzeptieren, da er es nicht zu Ende lesen kann).

Im Beispiel der Abbildung mit dem Wort \(abba\) wird nun zuerst das \(a\) gelesen und dabei der Zustandswechsel nach \(z_1\) gemacht (Abbildung 2.5). Dort können dann mittels der \(b\)-Schleife die beiden \(b\) gelesen werden und im Anschluss wird mit der \(a\)-Kante von \(z_1\) nach \(z_2\) in den Zustand \(z_2\) gewechselt (Abbildung 2.6).

Da \(z_2\) nun ein Endzustand ist und das Wort zu Ende gelesen wurde, wird \(abba\) akzeptiert. In Fällen, in denen der Automat bei einem Wort nicht diese beiden Bedingungen erfüllt, wird das Wort nicht akzeptiert.

Beispiel Überführungsfunktion

Sei \(A\) durch folgendes Zustandsübergangsdiagramm gegeben. Dann ist \(\hat{\delta}(z_0, 001) = \hat{\delta}(z_0, 01) = \hat{\delta}(z_0, 1) = z_1\) und abkürzend schreibt man dann einfach \(\hat{\delta}(z_0, 001) = z_1\) oder bricht an einer beliebigen für einen interessanten Stelle ab.

Beispiel Konfiguration und Rechnung

Sei wieder \(A\) durch folgendes Zustandsübergangsdiagramm gegeben. Dann ist bei Eingabe \(001\) die Konfiguration zu Beginn \((z_0, 001)\). Auf diesem Wort hat der Automat die Rechnung $$(z_0, 001) \vdash (z_0, 01) \vdash (z_0, 1) \vdash (z_1, \lambda)$$ Da die Rechnung in \((z_1, \lambda)\) endet und \(z_1\) ein Endzustand ist, ist dies sogar eine Erfolgsrechnung.

Zuletzt noch zwei Begriffe, die im Zusammenhang mit endlichen Automaten sowohl bei der Konstruktion als auch bei Beweisen öfter auftreten.

Ist ein Automat vollständig, so gibt es also zu jedem Symbol des Eingabealphabets eine Kante in jedem Zustand. Dies führt dazu, dass jede Eingabe (zu Ende) gelesen werden kann. Initial zusammenhängend bedeutet, dass jeder Zustand erreichbar ist. Dies ist bisweilen gut zu wissen, da die anderen Zustände im Grunde nutzlos sind. Man spricht auch von einer initialen Zusammenhangskomponente, wenn man die Zustände meint, die vom Startzustand aus erreichbar sind und schränkt einen DFA oft auf diese ein.

Im einzelnen ist ein Alphabet eine (total geordnete) endliche Menge von unterschiedlichen Zeichen (alternativ: Buchstaben oder Symbole). Wir notieren diese Menge meistens mit \(\Sigma\). Es ist dann z.B. \(\Sigma = \{a, b, c\}\) für das Alphabet mit den Zeichen \(a\), \(b\) und \(c\).

Die Konkatenation wird mit \(\cdot\) notiert und ist die Operation zum Hintereinanderschreiben von Buchstaben. So ergeben sich Worte, auf die die Operation dann erweitert wird. Z.B. ist \(a \cdot b = ab\) und dann \(ab \cdot c = abc\). Diese Konkatenation wird auf Mengen von Wörtern erweitert, so dass wir z.B.

$$\{ab, aba\} \cdot \{ab, b\} = \{ab \cdot ab, ab \cdot b, aba \cdot ab, aba \cdot b \}$$

erhalten (was das gleiche ist wie \(\{abab, abb, abaab\}\), da der \(\cdot\) oft weggelassen wird.

Das leere Wort (das Wort mit \(0\) Buchstaben) wird mit \(\lambda\) oder \(\epsilon\) bezeichnet. Es ist nie in einem Alphabet enthalten, sondern ist das spezielle Wort das aus \(0\) Symbolen eines Alphabets besteht.

Mit \(|w|\) wird die Länge eines Wortes \(w\) notiert. Z.B. ist \(|001| = 3\), \(|00111| = 5\) und \(|\lambda| = 0\). Mit \(|w|_x\) ist die Anzahl der \(x\) in \(w\) gemeint, wobei \(x\) ein Symbol ist, z.B. ist \(|2202|_2 = 3\).

Als weitere Notation schreiben wir \(w^1 = w, w^2 = w \cdot w\) und \(w^k = w^{k-1} \cdot w\) (\(k \geq 2\)) und als Spezialfall \(w^0 = \lambda\). Die hochgestellte Zahl \(i\) bei \(w^i\) gibt also an, wie oft wir ein Wort hintereinander schreiben wollen. Ähnlich wie oben erweitern wir diese Operation auf Mengen, so dass wir für eine Menge von Worten \(R\) dann \(R^1 = R\), \(R^2 = R \cdot R\) und allgemein \(R^n = R^{n-1} \cdot R\) haben (Spezialfall: \(R^0 = \{\lambda\}\)). In \(R^i\) sind also alle Wörter enthalten, die man erhält, wenn man \(i\) Wörter aus \(R\) auswählt und diese hintereinander schreibt.

Zuletzt zwei besonders wichtige Definitionen, die auf obigem aufbauen. Wir setzen

In \(R^+\) sind also jene Wörter, die man erhält, wenn man beliebig oft (aber endlich oft!) Wörter aus \(R\) hintereinander schreibt und in \(R^*\) ist zusätzlich auf jeden Fall noch \(\lambda\) enthalten (\(\lambda\) kann auch in \(R^+\) enthalten sein, aber nur wenn \(\lambda \in R\) gilt).

Besonders wichtig ist für uns der Spezialfall \(\Sigma^*\) für ein Alphabet \(\Sigma\). Dabei ist \(\Sigma^*\) dann die Menge aller endlichen Wörter (über dem Alphabet \(\Sigma\)). Jede (Teil-)Menge \(L \subseteq \Sigma^*\) heißt formale Sprache.

Wir fassen die vielen Definitionen noch einmal zusammen.

 
In diesem Kapitel wollen wir den endlichen Automaten einführen, das einfachste Automatenmodell, das aber recht nützlich ist und als Grundlage für weitere Automatenmodell dient.

Um uns diesem zu nähern, betrachten wir zunächst einen einfachen Lichtschalter. Dieser kann 'an' oder 'aus' sein, also in genau einem von zwei Zuständen. Zudem sind durch die Aktion 'Schalter betätigen' Zustandsübergänge möglich. Abbildung 2.1 zeigt eine graphische Darstellung. Die Kantenbeschriftung \(b\) steht dabei für die Betätigung des Schalters.

Gehen wir nun davon aus, dass der Lichtschalter zu Beginn ausgeschaltet ist, so soll der Zustand 'aus' zudem der (eindeutige) Startzustand sein. Wollen wir ferner bspw. ein System modellieren, in dem nur jene Aktionsfolgen „gut“ sind, bei denen das Licht am Ende wieder ausgeschaltet ist, so modellieren wir den Zustand 'aus' noch als Endzustand. Abbildung 2.2 zeigt das ergänzte System. Der Pfeil in den Zustand 'aus' hinein deutet an, dass 'aus' der Startzustand ist. Der doppelte Kreis um 'aus' bedeutet, dass 'aus' ein Endzustand ist.

Damit haben wir bereits alle Komponenten eines endlichen Automaten vorliegen.
Wichtig ist bei diesem Beispiel, dass

• wir ein System mit einer endlichen Anzahl von Zuständen haben,
• von denen einer als Startzustand und
• eine beliebige Teilmenge als Endzustände hervorgehoben sind,
• dass Zustandsübergänge möglich sind und
• dass das System sich stets in genau einem Zustand befindet.

 

Während die bisher skizzierte Idee eines Systems mit Aktionen recht intuitiv ist (man denke z.B. an einen Fahrkarten- oder einen Süßigkeitenautomaten, die stets in einem Zustand sind und durch Aktionen in andere Zustände überführt werden), wird in der (theoretischen) Informatik meist eine andere Modellvorstellung verwendet. Die beiden Vorstellungen können aber ineinander überführt werden und sind daher im Grunde identisch. Die in der Informatik gängige Vorstellung ist die eines Automaten, der ein Eingabewort auf einem Eingabeband hat und dieses Wort Buchstabe für Buchstabe liest. Abbildung 2.3 zeigt eine skizzenhafte Darstellung. Dieser Automat besitzt drei Zustände,\(z_0\),\(z_1\),\(z_2\), wobei\(z_0\) der Startzustand und\(z_2\) ein Endzustand ist. An den Kantenbeschriftungen kann man zudem erkennen, dass er\(a\)s und\(b\)s lesen kann.

 

Das Eingabeband ist über dem Automaten notiert. Das Eingabewort ist \(abba\) (die weiteren leeren Kästchen und die schwarzen Punkte sollen andeuten, dass man auch längere Worte auf diesem Band notieren kann) und der gestrichelte Pfeil zwischen Automat und Eingabeband zeigt an, welcher Buchstabe des Wortes gerade gelesen wird (man spricht hier auch vom Lesekopf). Ist der Automat zu Anfang in \(z_0\), so kann er nun das \(a\) lesen (da es eine \(a\)-Kante aus \(z_0\) heraus gibt). Der Automat wechselt dann in den Zustand \(z_1\) und der Lesekopf wandert ein Feld weiter. Nun können die zwei \(b\) gelesen werden, wobei der Automat im Zustand \(z_1\) bleibt. Der letzte Buchstabe (das \(a\)) kann dann auch gelesen werden, wobei der Automat in den Zustand \(z_2\) wechselt. Da dies ein Endzustand ist und das Wort bis zum Ende gelesen wurde, akzeptiert der Automat das Wort \(abba\).

Die Vorstellung eines Eingabebandes ist historisch gewachsen und erscheint heute eher altertümlich. Sie ist aber eine gute Abstraktion und man kann sich recht gut überlegen, dass die Vorstellungen eines Wortes im (Haupt-)Speicher oder einer Folge von Aktionen wie zu Anfang recht ähnlich sind. Das wichtige ist hier der Automat, der ein Wort von links nach rechts liest und dieses letztendlich akzeptiert oder nicht. Nicht akzeptiert wird dabei ein Wort dann, wenn entweder das Wort gar nicht zu Ende gelesen werden kann (dies tritt auf, wenn der Automat in einem Zustand \(z\) ist und einen Buchstaben \(x\) lesen soll, zu dem es keine Kante aus \(z\) heraus gibt; man sagt dann, der Automat blockiert) oder aber das Wort zu Ende gelesen werden kann, der Automat dann aber nicht in einem Endzustand ist.

Die Menge aller Wörter, die ein gegebener Automat akzeptiert, bezeichnen wir als seine akzeptierte Sprache. Warum diese wichtig ist, werden wir in der Vorlesung genauer behandeln. Im obigen Beispiel aus Abbildung 2.2 akzeptieren wir z.B. genau die Wörter, die nur aus \(b\)s bestehen und die eine gerade Anzahl \(b\)s enthalten. Im Beispiel aus Abbidlung 2.3 werden jene Wörter aus \(a\)s und \(b\)s akzeptiert, die mit genau einem \(a\) beginnen und enden und die dazwischen beliebig viele (auch \(0\)) \(b\)s haben.

Man kann sich die Frage stellen, ob solche Automaten einen Anwendungsfall haben, da sie recht einfach erscheinen. Erstens sind solche endlichen Automaten die Grundlage für prinzipiell alle weiteren Automatenmodelle, mit denen dann sehr viel komplexere Systeme modelliert werden können. Zweitens sind bereits endliche Automaten für viele Anwendungen von Bedeutung. Bspw. basiert die Worterkennung bei einem Compiler (um bspw. das Schlüsselwort 'if' zu finden) auf endlichen Automaten. Auch Protokolle und viele Anwendungen aus der technischen Informatik lassen sich mit endlichen Automaten (oder leichten Varianten davon) modellieren und dann implementieren (nachdem sich das Modell als hoffentlich fehlerfrei erwiesen hat).