Endliche Automaten und reguläre Sprachen

Zwei Werkzeuge, die zunächst nichts miteinander zu tun haben: Ein Automat liest eine Zeichenfolge und entscheidet, ob sie zulässig ist. Eine Grammatik erzeugt Zeichenfolgen aus Regeln.

Das eine prüft, das andere produziert. Und trotzdem beschreiben sie in einem wichtigen Fall exakt dieselben Sprachen.

Dieser Zusammenhang ist eines der schönsten Ergebnisse der theoretischen Informatik. Er erlaubt, zwischen beiden Sichten zu wechseln, je nachdem, welche gerade die einfachere ist. Und er zeigt genau, wo die Grenze des Automatenmodells liegt.

Vorausgesetzt werden Zustand, Startzustand, Übergänge, Endzustände und die Übergangstabelle aus Automaten und Zustandsdiagramme, dazu Alphabet, Wort und Sprache aus dem vorigen Kapitel.

Neu ist hier die Sprachsicht: Ein Automat wird nicht mehr als Beschreibung eines Geräts benutzt, sondern als Entscheider über eine Menge von Wörtern.

Man lässt den Automaten ein Wort Zeichen für Zeichen lesen und schaut, wo er endet:

Ein Wort wird akzeptiert, wenn der Automat nach dem letzten Zeichen in einem Endzustand steht. Die von ihm erkannte Sprache ist die Menge aller akzeptierten Wörter.

Sprachen, für die es einen endlichen Automaten gibt, heißen regulär.

Beispiel: alle Wörter über $\{a, b\}$, die auf $ab$ enden.

        b            a            b
  →(S0) ──→ S0   (S0) ──→ (S1)  (S1) ──→ ((S2))

Vollständige Übergangstabelle:

Beachte die Zeile $S_2$: Nach einem gefundenen $ab$ geht es normal weiter, denn es können noch Zeichen folgen. Entscheidend ist allein, wo der Automat am Ende steht.

Jetzt der überraschende Teil. Aus einem Automaten lässt sich eine Grammatik ablesen, und zwar mechanisch:

• Jeder Zustand wird ein Nichtterminal.
• Jeder Übergang $X \xrightarrow{c} Y$ wird eine Regel $X \to c\,Y$.
• Jeder Endzustand $E$ bekommt zusätzlich die Regel $E \to \varepsilon$.

Für den Automaten oben:

S0 → a S1 | b S0
S1 → a S1 | b S2
S2 → a S1 | b S0 | ε

Diese Grammatik erzeugt genau die Wörter, die der Automat akzeptiert. Umgekehrt lässt sich aus jeder Grammatik dieser Form ein Automat bauen.

🔴 Solche Grammatiken heißen regulär: Auf der rechten Seite jeder Regel steht höchstens ein Nichtterminal, und es steht ganz rechts. Damit gilt:

Eine Sprache ist genau dann regulär, wenn es einen endlichen Automaten für sie gibt, und genau dann, wenn es eine reguläre Grammatik für sie gibt.

Der praktische Nutzen liegt im Wechseln der Sicht. Ein Automat ist leichter zu prüfen, weil man Wörter einfach durchlaufen lassen kann. Eine Grammatik ist leichter zu erweitern, weil man Regeln ergänzt. Man wählt, was gerade passt.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Ein Automat heißt deterministisch, wenn zu jedem Paar aus Zustand und Eingabezeichen genau ein Folgezustand festgelegt ist. Genau das leistet eine vollständig ausgefüllte Übergangstabelle.

Erlaubt man mehrere mögliche Folgezustände, spricht man von einem nichtdeterministischen Automaten. Er akzeptiert ein Wort, wenn es mindestens einen Weg gibt, der in einem Endzustand endet.

Nichtdeterministische Automaten sind oft viel kleiner und leichter zu entwerfen. Für „enthält irgendwo die Folge $ab$" genügt ein Automat, der einfach an einer beliebigen Stelle „rät", dass hier das gesuchte $ab$ beginnt.

Der wichtige Satz dazu lautet: Beide Bauarten erkennen genau dieselben Sprachen. Zu jedem nichtdeterministischen Automaten lässt sich ein deterministischer bauen, dessen Zustände die Mengen der jeweils möglichen Zustände des ursprünglichen sind. Der Preis ist die Größe: Aus $n$ Zuständen können im ungünstigsten Fall $2^n$ werden.

Praktisch heißt das: Man entwirft bequem nichtdeterministisch und lässt umwandeln. Die Ausdruckskraft gewinnt man dadurch nicht, nur Bequemlichkeit.

In Klasse 10 stand die Behauptung, dass kein endlicher Automat gleich viele öffnende wie schließende Klammern zählen kann. Jetzt lässt sich das beweisen, und der Beweis ist kurz.

Betrachte $L = \{a^n b^n \mid n \ge 1\}$, also die Sprache aus dem vorigen Kapitel.

Annahme: Es gäbe einen endlichen Automaten $A$ für $L$. Er hat eine feste Zahl $k$ von Zuständen.

Schritt 1: Wir lassen $A$ die Wörter $a, aa, aaa, \ldots, a^{k+1}$ lesen und notieren, in welchem Zustand er jeweils steht. Das sind $k+1$ Zustände bei nur $k$ verfügbaren.

Schritt 2: Nach dem Schubfachprinzip müssen zwei davon gleich sein. Es gibt also $i \neq j$ mit: Nach $a^i$ und nach $a^j$ befindet sich $A$ im selben Zustand.

Schritt 3: Ab diesem Punkt kann $A$ die beiden Fälle nicht mehr unterscheiden, denn sein Zustand ist alles, was er sich merkt. Was auch immer nun folgt, er behandelt beide gleich.

Schritt 4: Nun folge $b^i$. Das Wort $a^i b^i$ gehört zu $L$ und muss akzeptiert werden. Also endet $A$ in einem Endzustand. Da $a^j$ denselben Zustand erreicht hatte, akzeptiert $A$ auch $a^j b^i$. Wegen $i \neq j$ gehört dieses Wort aber nicht zu $L$.

Widerspruch. Also gibt es keinen solchen Automaten, und $L$ ist nicht regulär.

🔴 Halte fest, was hier bewiesen wurde: nicht „man hat keinen gefunden", sondern „es kann keinen geben". Die Ursache ist ausschließlich die Endlichkeit der Zustandsmenge. Ein Automat kann nur endlich viel unterscheiden, und unbegrenztes Zählen verlangt unendlich viele Unterscheidungen.

Trotz dieser Grenze sind sie außerordentlich nützlich, weil sehr viele praktische Prüfungen regulär sind:

• Ist das eine gültige Postleitzahl, Uhrzeit, IBAN?
• Beginnt der Bezeichner mit einem Buchstaben?
• Findet sich dieses Muster im Text?

Genau dafür gibt es reguläre Ausdrücke, eine kompakte Schreibweise für reguläre Sprachen. Sie stecken in jeder Suchfunktion und jeder Eingabeprüfung, und intern arbeitet dort ein endlicher Automat.

Die Kehrseite folgt aus dem Beweis oben: Verschachtelte Strukturen wie Klammerungen, HTML oder Programmquelltext sind nicht regulär. Wer sie mit regulären Ausdrücken prüfen will, scheitert nicht an mangelndem Geschick, sondern an einer beweisbaren Grenze des Modells.