4.4 Von einer regulären Grammatik zu einem endlichen Automaten

In diesem Unterkapitel wollen wir das Gelernte an einem konkreten Beispiel anwenden. Wir beginnen (1) mit einer Beschreibung eines Formats in natürlicher Sprache; (2) basteln uns daraus mit Hilfe des "Baukastenprinzips" eine reguläre Sprache; (3) säubern diese, indem wir Regeln der Form $X\to Y$ und $X\to a$ eliminieren; (4) bauen einen nichtdeterministischen endlichen Automaten; (5) transformieren diesen in einen deterministischen endlichen Automaten.

1. Beschreibung des Formats in natürlicher Sprache

Unsere Sprache $L$ soll so ähnlich sein wie die der erlaubten Domainnamen, allerdings mit ein paar Abänderungen, um die obigen Transformationen spannender zu machen. Ein Wort in unserer Sprache besteht aus einer nichtleeren Folge von Labels die jeweils durch einen . separiert sind. Jedes Label ist eine nichtleere Folge von Blöcken (ein nichtleerer String aus Buchstaben und Zahlen), separiert durch : oder - aber niemals durch beides innerhalb eines Blockes. Also:

ist ein Wort in $L$, aber ist kein Wort in $L$, da das erste Label die Separatoren : und - mischt. Habe ich $L$ genau genug beschrieben? Stellen wir eine Meta-Frage: Was zählt überhaupt als genaue Beschreibung einer Sprache? Wir können uns dem Mund fusselig reden und Beispiele und Nicht-Beispiele angeben, am Ende aber werden wir irgendwann beginnen, formale Regeln aufzustellen, die unsere Sprache beschreiben - wir werden also im Prinzip eine Grammatik schreiben. Tun wir dies also.

2. Eine reguläre Grammatik

Beginnen wir mit dem Alphabet. Da es 62 alphanumerische Zeichen gibt: a..zA..Z0..9 und wir uns keine unnötige Arbeit machen wollen, beschränken wir uns auf ein Zeichen: a. Dazu kommen die Separatoren :-.. Also: $\mathrm{\Sigma }=\{a,.,:,-\}$. Stellen Sie sich einfach vor, $a$ stehe für beliebige alphanumerische Zeichen. Sowohl Grammatik als auch Automaten lassen sich einfach anpassen. Wir beginnen ganz unten und schreiben eine Grammatik für Blöcke, also nichtleere Strings aus alphanumerischen Zeichen.

$$\begin{array}{rl}B& \to a|aB\end{array}$$

Als nächstes führen wir ein nichtterminales Symbole $C$ für Labels mit : ein und ein Nichtterminal $D$ für Labels mit -. Wir wählen die Buchstaben $C,D$, weil : auf Englisch colon und - dash heißt. $C$-Labels können wir uns nach dem Baukastenprizip bauen, in dem wir Theorem 4.1.14 anwenden. Wir fügen zur "End-Produktion" $B\to a$ eine weiter Produktion $B\to a:B$ hinzu und tun das gleiche für $B\to b$. Allerdings benennen wir $B$ in $C$ um, damit keine Verwechslungsgefahr mit dem ursprünglichen $B$ aufkommt. Das gleiche machen wir für $D$.

$$\begin{array}{rl}C& \to a|aC|a:C\\ D& \to a|aD|a-D\\ T& \to C|D\end{array}$$

Von $L$ lassen sich nun also alle Labels ableiten. Wir brauchen nun zum Schluss wieder eine Folge von $L$, mit . separiert, müssen also wieder Theorem 4.1.14 anwenden, dieses mal auf die von $T$ erzeugte Sprache. Im Ergebnis benennen wir das Startsymbol in $S$ um.

$$\begin{array}{rl}S& \to C|D\\ C& \to a|aC|a:C|a.S\\ D& \to a|aD|a\text{-}D|a.S\end{array}$$

Um eine "richtig" reguläre Sprache zu erhalten, entzerren wir die erweitert regulären Produktionen wie $C\to a:C$. Dafür brauchen wir neue Symbole $C^{\prime },D^{\prime },S^{\prime }$:

$$\begin{array}{rl}S& \to C|D\\ C& \to a|aC|a{C}^{\prime }|a{S}^{\prime }\\ C^{\prime }& \to :C\\ D& \to a|aD|a{D}^{\prime }|a{S}^{\prime }\\ D^{\prime }& \to \text{-}D\\ S^{\prime }& \to .S\end{array}$$

3. Die reguläre Grammatik säubern

Wir wollen nun alle Produktionen der Form $Y\to x$ eliminieren. Hierfür nehmen wir uns ein neues Nichtterminal $E$ und ersetzen $Y\to x$ durch $Y\to xE$ und fügen die Produktion $E\to ϵ$ hinzu.

$$\begin{array}{rl}S& \to C|D\\ C& \to aE|aC|a{C}^{\prime }|a{S}^{\prime }\\ C^{\prime }& \to :C\\ D& \to aE|aD|a{D}^{\prime }|a{S}^{\prime }\\ D^{\prime }& \to \text{-}D\\ S^{\prime }& \to .S\\ E& \to ϵ\end{array}$$

In einem zweiten Schritt wollen wir die Produktionen $S\to C$ und $S\to D$ eliminieren, sodass wir nur noch Produktionen der From $X\to aY$ und $E\to ϵ$ haben. Wir gehen vor wie in Theorem 4.1.7 beschrieben. Wir ersetzen $S\to C$ also durch alle Produktionen der Form $S\to \alpha$, wobei $\alpha$ eine Wortform ist, die sich aus $C$ ableiten lässt und nicht nur aus einem einzelnen Nichtterminal besteht; dies trifft glücklicherweise auf alle rechten Seiten der $C$-Produktionen zu; gleiches gilt für $D$. Wir erhalten:

$$\begin{array}{rl}S& \to aE|aC|a{C}^{\prime }|a{S}^{\prime }|aD|a{D}^{\prime }\\ C& \to aE|aC|a{C}^{\prime }|a{S}^{\prime }\\ C^{\prime }& \to :C\\ D& \to aE|aD|a{D}^{\prime }|a{S}^{\prime }\\ D^{\prime }& \to \text{-}D\\ S^{\prime }& \to .S\\ E& \to ϵ\end{array}$$

4. Einen nichtdeterministischen endlichen Automaten bauen

Dies sollte nun einfach sein. Wir erschaffen Zustände $S,C,C^{\prime },D,D^{\prime },S^{\prime },E$ und übersetzen jeden Grammatik-Pfeil in einen Automaten-Pfeil.

Ich habe die Zeichen .:- rot unterlegt, weil man sie sonst kaum erkennen würde in dem Automaten.

5. Den nichtdeterministischen Automaten in einen deterministischen umwandeln

Unser nichtdeterministischer endlicher Automat hat Zustandsmenge $Q=\{S,S^{\prime },C,C^{\prime },D,D^{\prime },E\}$, also insgesamt sieben Zustände. Wenn wir genau nach Buch vorgingen, müssten wir den endlichen Automaten auf der Zustandsmenge $2^Q$ definieren, er hätte also $2^7=128$ viele Zustände. Das wäre jetzt für einen Rechner kein Problem, aber in diesem vorlesungsskript doch etwas ungünstig. Wir gehen lazy vor, erschaffen Zustände in $2^Q$ also nur dann, wenn wir sie brauchen. Wir beginnen mit dem Zustand $\{S\}$ und legen dann an jeden Zustand Kanten an, jeweils mit $a,:,-,.$ beschriftet, und erschaffen, falls nötig, dabei neue Zustände. In der folgenden Animation sehen Sie manchmal den mit einem Kreuz markierten Fehlerzustand (trap state). Die akzeptierenden Zustände sind mit fettem Rand markiert.

Der nichtdeterministische Automat

Der deterministische Automat, Schritt für Schritt gebaut:

Dieser Automat hat deutlich weniger also 128 Zustände, nämlich mit nur sieben genau so viele wie der nichtdeterministische (es ist Zufall, dass beide gleich viele Zustände haben; messen Sie dieser Tatsache keine Bedeutung bei). Wir könnten nun von diesem Automaten ausgehend wiederum eine reguläre Grammtik bauen, die in diesem Falle sogar einfacher und klarer wäre als die ursprüngliche. Wenn wir erweitert reguläre Grammatiken erlauben, so können wir den deterministischen Automaten besonders konzise in eine Grammatik fassen:

$$

Die Zustände des deterministischen Automaten beschreiben im Prinzip das, was wir uns merken müssen, wenn wir so einen String "parsen": Zustand $$, der in der Grammatik dann zum Nichtterminal $$ wird, bedeutet beispielsweise das Label hat schon begonnen, wir wissen aber noch nicht, ob es eines mit : oder eines mit - ist. Der Zustand $$ bzw. das Nichtterminal $$ heißt dann wir sind innerhalb eines Labels mit :.