Formale Sprachen und Automaten

Alphabet, Wort, Sprache

Die Theorie beginnt mit drei Begriffen. Ein Alphabet ist eine endliche Menge von Zeichen, etwa {0, 1} oder {a, b}. Ein Wort ist eine endliche Folge davon – auch das leere Wort ε zählt. Eine Sprache ist eine beliebige Menge von Wörtern, meist unendlich groß.

Das klingt abstrakt, deckt aber fast alles ab: „Alle syntaktisch korrekten Java-Programme“ ist eine Sprache über dem Unicode-Alphabet. „Alle E-Mail-Adressen“ auch. Und jede Ja/Nein-Frage an einen Computer lässt sich so formulieren: Gehört diese Eingabe zur Sprache der Eingaben, bei denen die Antwort „ja“ ist?

Der endliche Automat

Ein deterministischer endlicher Automat (DFA) besteht aus Zuständen, einem Startzustand, einigen akzeptierenden Zuständen und einer Übergangstabelle: Für jeden Zustand und jedes Zeichen steht fest, wohin es geht. Er liest die Eingabe einmal von links nach rechts – und am Ende entscheidet allein der Zustand, in dem er steht. Probier es aus:

Das Bemerkenswerte am dritten Beispiel: Der Automat prüft die Teilbarkeit beliebig langer Binärzahlen mit nur drei Zuständen – er merkt sich nur den Rest. Jedes neue Bit verdoppelt die Zahl und addiert 0 oder 1, also wird aus Rest r der Rest (2r + Bit) mod 3. Mehr muss er nicht wissen.

Regex und Automat sind dasselbe

Ein zentraler Satz der Theorie (nach Stephen Kleene, 1956): Zu jedem regulären Ausdruck gibt es einen endlichen Automaten, der genau dieselbe Sprache erkennt – und umgekehrt. Ein regulärer Ausdruck ist die Beschreibung, der Automat die Maschine. Regex-Bibliotheken übersetzen den Ausdruck in einen Automaten, oft zuerst in einen nichtdeterministischen (NFA), der an einer Stelle mehrere Wege offenhalten darf. Ein NFA kann nicht mehr als ein DFA, ist aber oft viel kleiner; man kann ihn in einen DFA umrechnen, der dann allerdings im schlimmsten Fall exponentiell viele Zustände hat.

Streng genommen sind die Ausdrücke in Java, Perl oder JavaScript mehr als „regulär“: Rückverweise wie (a+)\1 gehen über das hinaus, was ein endlicher Automat kann. Der Preis dafür kommt weiter unten.

Was ein Automat nicht kann

Ein Automat hat keinen Speicher außer seinem Zustand – und davon nur endlich viele. Deshalb kann er nicht beliebig weit zählen. Das klassische Beispiel sind korrekt verschachtelte Klammern: Um zu prüfen, ob auf n öffnende auch n schließende folgen, müsste er sich n merken. Stell ein, wie viele Zustände der Automat hat und wie tief verschachtelt wird:

Daraus folgt eine Regel für die Praxis: Verschachtelte Strukturen – HTML, JSON, XML, Programmcode, arithmetische Ausdrücke – lassen sich nicht zuverlässig mit einem Regex prüfen. Man braucht einen Parser. Ein Regex taugt dafür, die einzelnen Bausteine (Zahlen, Bezeichner, Zeichenketten) zu erkennen – genau so arbeitet ein Compiler: Der Lexer ist ein Automat, der Parser darüber kann verschachteln.

Die Chomsky-Hierarchie

Gibt man dem Automaten mehr Speicher, kann er mehr Sprachen erkennen. Noam Chomsky ordnete die Sprachklassen 1956 in eine Hierarchie, die bis heute den Bau von Compilern prägt:

Ein Stapel reicht für Klammern: bei „(“ drauflegen, bei „)“ herunternehmen, am Ende muss er leer sein. Genau das macht jeder Parser – und jeder Entwickler, der die Klammerprüfung in einer Bewerbung programmieren soll. Die letzte Zeile ist das Thema der nächsten Seite.

Wenn ein Regex hängt

Ein echter DFA liest jedes Zeichen genau einmal – seine Laufzeit ist linear, egal wie der Ausdruck aussieht. Die Regex-Engines von Java, JavaScript, Python und Perl arbeiten aber anders: Sie probieren Möglichkeiten nacheinander aus und gehen bei einem Fehlschlag zurück (Backtracking). Das macht Rückverweise möglich, kann aber bei ungünstigen Mustern explodieren. Das Muster (a+)+b auf eine Folge von n mal „a“ ohne „b“ am Ende:

Das Problem entsteht durch verschachtelte Wiederholungen, die dieselben Zeichen auf viele Arten aufteilen können: n Zeichen lassen sich auf 2ⁿ⁻¹ Arten in Gruppen zerlegen, und die Engine probiert jede, bevor sie aufgibt. Weil das auch mit Absicht ausgelöst werden kann, gilt es als Sicherheitsthema (ReDoS). Abhilfe: Muster ohne verschachtelte Quantoren schreiben, possessive Quantoren oder atomare Gruppen nutzen, Eingabelängen begrenzen – oder eine Engine mit garantierter Linearzeit verwenden, wie Googles RE2, das auf Rückverweise verzichtet.

Für Entwickler übersetzt

// Ein DFA in Java: Zustand als enum, Übergänge als switch
enum Z { START, MINUS, ZIFFERN, FEHLER }

static boolean istGanzzahl(String s) {
    Z z = Z.START;
    for (char c : s.toCharArray()) {
        boolean ziffer = c >= '0' && c <= '9';
        z = switch (z) {
            case START   -> c == '-' ? Z.MINUS : ziffer ? Z.ZIFFERN : Z.FEHLER;
            case MINUS, ZIFFERN -> ziffer ? Z.ZIFFERN : Z.FEHLER;
            case FEHLER  -> Z.FEHLER;
        };
    }
    return z == Z.ZIFFERN;     // einziger akzeptierender Zustand
}

// Dasselbe als Regex – Pattern einmal kompilieren, nicht bei jedem Aufruf
private static final Pattern GANZZAHL = Pattern.compile("-?[0-9]+");
boolean ok = GANZZAHL.matcher(s).matches();

// Backtracking vermeiden: possessiver Quantor gibt einmal Erfasstes nicht wieder her
Pattern.compile("(a++)+b");   // scheitert sofort statt exponentiell

Häufige Irrtümer

Verwandte Begriffe