4.2 Endliche Automaten

Grammatiken erlauben es uns, gewisse Formate zu beschreiben. Das reicht uns aber nicht: wir wollen Daten parsen, im engen Sinne also eine grammatische Ableitung rekonstruieren und allgemein die Struktur eines gegebenen Wortes herausarbeiten. Ein bescheideneres Ziel ist es, für ein gegebenes Wort zu entscheiden, ob es sich überhaupt aus einer Grammatik ableiten lässt. Für reguläre Grammatiken gibt es hierfür die endlichen Automaten. Sie können endliche Automaten verstehen als ein eingeschränktes Modell eines Rechners; oder als Blaupause für einen effizienten Algorithmus, um reguläre Grammatiken zu parsen.

Hier sehen Sie ein Beispiel für einen endlichen Automaten über dem Alphabet Σ={x,y,z}. Die Idee ist, dass der Automat ein Wort α Zeichen für Zeichen einliest. Die Pfeile zwischen den Kreisen (den Zuständen des Automaten) zeigen an, in welchen neuen Zustand beim Lesen eines Zeichen gewechselt werden muss. Der Pfeil "aus dem Nichts", hier der von links nach S, zeigt den Startzustand an, in welchem der Automat beginnt.

Um zu zeigen, wie der Automat ein Eingabewort verarbeitet, nehmen wir das Beispiel α=yxzxxyy.

In diesem Beispiel endet der Automat im Zustand . Sie sehen, dass der Zustand mit einem doppelten Rand markiert ist: dies symbolisiert, dass ein akzeptierender Endzustand ist. Wenn der Automat ein Wort abgearbeitet hat, akzeptiert er es, wenn er in einem akzeptierenden Endzustand gelandet ist; ansonsten lehnt er es ab. In unserem Beispiel sehen wir also, dass der Automat das Eingabewort ablehnt.

Definition 4.2.1 (Endlicher Automat, Finite State Machine). Ein endlicher Automat besteht aus einem endlichen Eingabealphaet , einer endlichen Menge von Zuständen, einem Startzustand , einer Menge von akzeptierenden Endzuständen und einer Zustandsübergangsfunktion Formal gesehen ist also ein Automat ein Quintupel .

Die Idee ist, dass der Automat im Zustand startet und nun in jedem Schritt ein weiteres Zeichen des Eingabewortes liest. Wenn er im Zustand ist und das Zeichen liest, so wechselt er in den Zustand . Statt verwenden wir die leichter zu lesende Schreibweise Wenn das Wort zu Ende ist, dann akzeptiert der Automat, wenn er in einem akzeptierenden Zustand angekommen ist, also in .

Definition 4.2.2 (Erweiterte Zuständsübergangsfunktion). Für einen endlichen Automaten definieren wir die erweiterte Zustandsübergangsfunktion rekursiv wie folgt: heißt also, dass der Automat, wenn er sich im Zustand befindet und das Wort abarbeitet, er danach im Zustand landet. Wir schreiben auch kompakt
Definition 4.2.3 (Akzeptierte Sprache). Sei ein endlicher Automat. Die von akzeptierte Sprache ist
Beispiel 4.2.4 Der endliche Automat, den wir oben bereits eingeführt haben:
akzeptiert die Sprache aller , die auf enden und nicht die Buchstabenfolge enthalten.
Übungsaufgabe 4.2.1 Ändern Sie den Automaten aus dem letzten Beispiel so ab, dass die Bedingung "die auf enden" entfällt, er also alle Wörter akzeptiert, die die Folge nicht enthalten.
Übungsaufgabe 4.2.2 Zeichnen Sie einen Automaten für die Sprache aller Wörter über , die die Folge enthalten.
Übungsaufgabe 4.2.3 Zeichnen Sie einen Automaten für die Sprache aller Wörter über , die genau vier enthalten.

Endliche Automaten zu regulären Grammatiken

Wenn wir einen endlichen Automaten gegeben haben, dann können wir leicht eine entsprechende reguläre Grammatik dazu bauen, indem wir alle Pfeile einfach in Produktionen übersetzen. Für den Automaten
würde dies beispielsweise die folgenden Produktionen ergeben: und, weil ein akzeptierender Zustand ist, Dies geht ganz allgemein:
Theorem 4.2.5 Sei ein endlicher Automat. Dann gibt es eine reguläre Grammatik mit .

Wir nehmen dies als Anlass, um mal wieder einen Induktionsbeweis im Detail durchzuführen.

Beweis. Wir setzen und und führen für jeden Zustandsübergang, der von beschrieben wird, eine Ableitungsregel ein: Hiermit erhalten wir eine "Zwischengrammatik" . Die endgültige Grammatik erhalten wir, indem wir für jeden akzeptierenden Zustand die Produktion einführen. Wir zeigen nun per Induktion:
Behauptung 4.2.6 Sei und . Dann gilt genau dann, wenn in Grammatik gilt.

Bevor wir diese Behauptung beweisen, achten Sie auf die Bedeutung der Symbole. Der einfache Pfeil in beschreibt die Arbeitsweise des endlichen Automaten, dass nämlich das Verarbeiten von den Automaten vom Zustand in den Zustand führt. Der doppelte Pfeil in sagt aus, dass aus dem Nichtterminalsymbol in der Grammatik in möglicherweise mehreren Schritten die Wortform abgeleitet werden kann. Der Pfeil "lebt" also im Automaten , der Pfeil lebt in der Grammatik .

Beweis. Wir verwenden Induktion über die Länge des Wortes .

Induktionsbasis. Wenn gilt, also die Länge 0 hat, dann gilt genau dann, wenn ist. Wie kann nun in gelten? Beachten Sie, dass jede Produktion in ein Terminalsymbol erzeugt; kann also nur gelten, wenn keine Produktion erfolgt ist und somit gilt. Wir sehen: beide Aussagen sind äquivalent zu und somit auch äquivalent zueinander.

Induktionsschritt. Wenn die Länge hat, so schreiben wir für ein Wort der Länge . Per Induktionshypothese können wir nun davon ausgehen, dass für alle die Aussage genau dann gilt, wenn gilt. Unser Ziel ist es, zu zeigen, dass die beiden folgenden Aussagen äquivalent sind:

  1. im endlichen Automaten ,
  2. in der Grammatik .
Wir müssen beide Richtungen zeigen, also zeigen, dass aus Aussage (1) die Aussage (2) folgt und umgekehrt.

Aus (1) folgt (2). Nehmen wir also an, dass gilt und bezeichnen . Es gilt also Der erste Teil, also , bedeutet, dass wir in die Produktion eingeführt haben. Auf den zweiten Teil, also , können wir die Induktionshypothese anwenden und schließen, dass gilt. Nun können wir mit dem Nichtterminal beginnen, die Produktion anwenden und dann mit fortfahrend die Wortform ableiten, also Dies zeigt die erste Richtung.

Aus (2) folgt (1). Nun nehmen wir an, dass gilt. Untersuchen wir die erste Produktion, die in dieser Ableitung verwendet worden ist. Alle Produktionen in erzeugen ein Terminalsymbol, also muss es eine Produktion der Form gewesen sein. Die Ableitung hat also die Form wir können also aus die Wortform ableiten: . Auf diese Erkenntnis wenden wir die Induktionshypothese an und schließen, dass gilt. Die Produktionsregel kann nur in eingeführt worden sein, weil , also . Somit sehen wir, dass gilt, also zusammengenommen . Dies zeigt die zweite Richtung.

Hiermit endet der Induktionsbeweis.

Wir haben nun die Behauptung bewiesen. Als nächstens betrachten wir die Grammatik und behaupten, dass gilt. Sei , dann behaupten wir also, dass wir folgenden zwei Aussagen äquivalent sind:

  1. für einen Zustand ,
  2. in Grammatik .

Wenn nun also gilt und , dann wissen wir von der obigen Behauptung, dass es in die Ableitung gibt. Da ist, enthält die Produktion , und somit können wir in die Ableitung machen.

In der anderen Richtung, wenn in Grammatik gilt, dann betrachten wir den letzten Ableitungsschritt. Da keine Nichtterminalsymbole enthält, muss im letzten Ableitungsschritt ein Nichtterminalsymbol verschwunden sein. Die einzigen Produktionen in bei denen das Nichtterminal verschwindet, sind von der Form , wenn im Automaten ein akzeptierender Endzustand ist. Sei nun also die Produktion, die im letzten Ableitungsschritt angewendet worden ist. Es gilt also . Beachten Sie nun weiter, dass all jene Produktionen, die in aber nicht in sind, die Form haben, also das Nichtterminalsymbol verschwinden lassen; es kann in einer Ableitung also nur eine solche Produktion angewandt worden sein, und das ganz zum Schluss. Das heißt: die Ableitung verwendet ausschließlich -Produktionen. Somit können wir die oben gezeigte Behauptung anwenden und folgern, dass gilt. Dies ist genau Punkt 1, den wir zeigen wollten.

Beachten Sie, dass dieser Beweis eigentlich gar nicht so schwierig ist, wie er hier aussieht. Ich habe ihn absichtlich sehr formal und ausführlich geschrieben, um Ihnen das Prinzip des Induktionsbeweises ins Gedächtnis zu rufen.

Übungsaufgabe 4.2.4 Schreiben Sie zu folgendem Automaten über dem Alphabet eine äquivalente reguläre Grammatik:
und beschreiben Sie die Sprache in eigenen Worten.

Reguläre Grammatiken zu endlichen Automaten?

Im letzten Abschnitt haben wir gesehen, wie wir zu einem gegebenen endlichen Automaten recht einfach eine äquivalente reguläre Grammatik schreibne können. Es drängt sich die Frage auf: geht das auch umgekehrt? Versuchen wir es. Zu jedem "Grammatik-Pfeil" bauen wir uns einen "Automaten-Pfeil" .

Beispiel 4.2.7 Betrachten wir die reguläre Grammatik aus dem vorherigen Kapitel 4.1:

Versuchen wir, daraus einen endlichen Automaten zu bauen. Als Zustandsmenge nehmen wir die Menge nichtterminaler Symbole , als Startzustand das Startsymbol . Zustandsübergänge ergeben sich aus den Produktionsregeln, wobei wir für Produktionen der Form den Zustand zu einem Endzustand machen. Also:

Wie Sie sehen, ist das nicht ganz korrekt. Als erstes fällt ins Auge, dass alle Zustände akzeptierende Endzustände sind. Als zweites fällt uns auf, dass es bei für das Eingabesymbol keinen ausgehenden Pfeil gibt. Der Funktionswert ist also undefiniert. Der Grund hierfür ist, dass, wenn erst mal ein vorgekommen ist, eben kein mehr vorkommen darf. Die Definition eines endlichen Automaten verlangt aber, dass eine Funktion ist, also für alle Eingabewerte definiert ist. Wir lösen das, indem wir einen sogenannten Fehlerzustand (Trap State) einführen, der im Prinzip den Zustand lehne das Wort ab, egal, was noch kommt versinnbildlicht:

Dies ist nun unser endlicher Automat mit .

Beispiel 4.2.8 Betrachten wir die reguläre Grammatik aus dem vorherigen Kapitel 4.1: Wobei wir aus dem vorherigen Beispiel lernen und einen Fehlerzustand einführen:

Leider ist diese Lösung auch nicht korrekt: jetzt gibt es zu viele Pfeile! Aus dem Zustand gehen zwei Pfeile mit beschriftet hinaus. Wenn wir uns vor Augen halten, was die von erzeugte Sprache ist, so wird das Problem klarer: erzeugt die Sprache aller Wörter über , deren viertletztes Zeichen eine 1 ist. Die Herausforderung ist nun: wenn der Automat eine 1 liest, dann weiß er nicht, ob das jetzt schon das viertletzte Zeichen ist oder nicht; er weiß also nicht, ob er im Zustand bleiben soll oder weiter zum Zustand gehen soll.

Um mit Fällen wie dem eben geschilderten umgehen zu können, erweitern wir die Definition des endlichen Automaten in nächsten Kapitel zu einem nichtdeterministischen endlichen Automaten.