Ohrfeige

Zu jedem regulären Ausdruck existiert ein endlicher Automat, der die vom Ausdruck spezifizierte Sprache akzeptiert. Ein entsprechender (nichtdeterministischer) endlicher Automat kann mit der Thompson-Konstruktion[3] aus einem regulären Ausdruck konstruiert werden. Daraus folgt die relativ einfache Implementierbarkeit regulärer Ausdrücke. Umgekehrt existiert zu jedem endlichen Automaten ein regulärer Ausdruck, der die vom Automaten akzeptierte Sprache beschreibt. Ein entsprechender regulärer Ausdruck kann mit Kleenes Algorithmus[1][4] aus einem nichtdeterministischen endlichen Automaten konstruiert werden. Kleenes Algorithmus erzeugt meist sehr lange reguläre Ausdrücke. Die Zustands-Elimination[4] (deutsch eigentlich: „Zustands-Eliminierung“) liefert in der Praxis meist kürzere reguläre Ausdrücke. Im schlimmsten Fall (englisch „worst case“) liefern jedoch beide Algorithmen reguläre Ausdrücke der Länge | Σ | 4 | Q | {\displaystyle |\Sigma |4^{|Q|}},[5] wobei | Σ | {\displaystyle |\Sigma |} die Anzahl der Zeichen des zugrundeliegenden Alphabets und | Q | {\displaystyle |Q|} die Anzahl der Zustände im Automaten bezeichnen.