Reguläre Ausdrücke benutzt fast jeder Entwickler täglich – aber kaum jemand weiß, was beim Matchen im Inneren passiert. Hinter jeder Regex steckt ein endlicher Automat, eine der elegantesten Ideen der theoretischen Informatik. Wer dieses Modell versteht, schreibt nicht nur bessere Ausdrücke, sondern versteht auch, warum manche Regex blitzschnell sind und andere einen Server lahmlegen.
Endliche Automaten: Zustände und Übergänge
Ein endlicher Automat (finite automaton) besteht aus einer endlichen Menge von Zuständen, einem Startzustand, mindestens einem Endzustand (akzeptierend) und Übergängen, die bei einem gelesenen Zeichen von einem Zustand in den nächsten führen. Der Automat liest die Eingabe Zeichen für Zeichen. Endet er nach dem letzten Zeichen in einem akzeptierenden Zustand, gilt das Wort als akzeptiert – die Regex matcht.
Die zentrale Erkenntnis: Jeder reguläre Ausdruck lässt sich in einen endlichen Automaten übersetzen und umgekehrt. Reguläre Ausdrücke und endliche Automaten beschreiben exakt dieselbe Sprachklasse – die regulären Sprachen.
NFA vs. DFA: zwei Sichtweisen
Es gibt zwei Varianten, die du kennen solltest:
- DFA (deterministischer endlicher Automat): Für jedes Zeichen gibt es aus jedem Zustand genau einen Folgezustand. Eindeutig, ohne Rückverfolgung, sehr schnell – aber oft mit vielen Zuständen.
- NFA (nichtdeterministischer endlicher Automat): Aus einem Zustand kann ein Zeichen zu mehreren Folgezuständen führen, und es gibt Epsilon-Übergänge (ε), die ohne Lesen eines Zeichens gewechselt werden. Der Automat ist gewissermaßen "in mehreren Zuständen gleichzeitig".
Beide sind gleich mächtig: Jeder NFA lässt sich per Potenzmengenkonstruktion in einen DFA umwandeln. Der NFA ist kompakter und leichter aus einer Regex zu bauen, der DFA ist schneller im Betrieb. Mit dem Regex-Automat kannst du genau diesen NFA zu einem regulären Ausdruck visualisieren und Teststrings live gegen den Automaten laufen lassen.
Die Thompson-Konstruktion: von der Regex zum NFA
Wie kommt man von einem Ausdruck wie (a|b)*c zu einem Automaten? Die klassische Antwort ist die Thompson-Konstruktion (benannt nach Ken Thompson, der sie 1968 beschrieb). Sie baut den NFA rekursiv aus kleinen Bausteinen zusammen – jeder Operator entspricht einem festen Schema:
- Einzelnes Zeichen
a: zwei Zustände, ein Übergang mitadazwischen. - Verkettung
ab: Der Endzustand des ersten Teils wird per Epsilon mit dem Start des zweiten verbunden. - Alternative
a|b: Ein neuer Startzustand verzweigt per Epsilon in beide Teilautomaten, deren Enden sich in einem gemeinsamen Endzustand treffen. - Stern
a*: Epsilon-Schleifen erlauben null, ein oder beliebig viele Wiederholungen.
Das Schöne: Jeder dieser Schritte erzeugt einen Teilautomaten mit genau einem Start- und einem Endzustand. Dadurch lassen sich die Bausteine beliebig schachteln, und der entstehende NFA wächst nur linear mit der Länge der Regex.
So matcht der Automat einen Teststring
Beim Matchen verfolgt die Engine die Menge aller aktuell möglichen Zustände gleichzeitig. Für jedes gelesene Zeichen berechnet sie alle erreichbaren Folgezustände und zieht anschließend alle Epsilon-Übergänge nach (die sogenannte Epsilon-Hülle). Ist nach dem letzten Zeichen ein akzeptierender Zustand in der Menge, ist der String ein Treffer.
Dieses Verfahren – die NFA-Simulation – läuft in linearer Zeit zur Eingabelänge. Genau das nutzen schnelle Engines wie RE2 oder die grep-Familie. Wer den Mechanismus einmal Schritt für Schritt im Regex-Automat beobachtet, versteht sofort, warum die Reihenfolge der Übergänge so wichtig ist.
Warum manche Regex katastrophal langsam werden
Viele verbreitete Sprachen (PCRE, Java, JavaScript, Python) nutzen statt der Automaten-Simulation einen Backtracking-Ansatz. Der ist mächtiger – er kann Rückbezüge und Lookarounds – aber anfällig für katastrophales Backtracking. Bei Ausdrücken wie (a+)+$ auf einem nicht passenden String probiert die Engine exponentiell viele Wege durch und hängt sich auf. Dieses Phänomen ist die Grundlage von ReDoS-Angriffen (Regular Expression Denial of Service).
Die Lehre: Wer reine, "echte" reguläre Ausdrücke schreibt – ohne Rückbezüge – kann auf eine Automaten-basierte Engine mit garantierter Linearzeit setzen und ist sicher. Verschachtelte Quantoren wie (x*)* solltest du dagegen meiden.
Was du daraus mitnimmst
Reguläre Ausdrücke sind keine magische Syntax, sondern eine kompakte Schreibweise für endliche Automaten. Wenn du das Modell aus Zuständen, Übergängen und Epsilon-Hüllen verinnerlichst, fällt dir das Debuggen komplexer Muster deutlich leichter. Probier deine Ausdrücke direkt im Regex-Automat aus. Für die klassische Praxis – Muster gegen Text testen und Treffer zählen – findest du im Regex Match Tester ein schlankes Werkzeug, und für sichere Literale hilft das Regex Escape Tool.