Umwandlung eines regulären Ausdrucks in einen Automaten

Wir zeigen, wie man einen beliebigen regulären Ausdruck in einen nichtdeterministischen endlichen Automaten umwandelt.

Beispiel

Bevor wir den eigentlichen Algorithmus beschreiben, zeigen wir an einem Beispiel, worum es uns eigentlich geht. Betrachten wir diesen regulären Ausdruck: a(b|c)x^∗. In Worten würden wir die Sprache, die der reguläre Ausdruck beschreibt, so beschreiben: Es sind Wörter, die mit dem Buchstaben „a“ beginnen, darauf folgt entweder der Buchstabe „b“ oder „c“ und danach eine beliebige Anzahl von Buchstaben „x“. Könnten wir einen Automaten konstruieren, der diese Sprache akzeptiert? Aber ja, schau her:

Dieser Automat akzeptiert offensichtlich dieselbe Sprache. Da drängt sich die Frage auf, ob es zu jedem regulären Ausdruck einen Automaten gibt, der die entsprechende Sprache akzeptiert. Nun, ja.

Beschreibung des Algorithmus zur Umwandlung eines regulären Ausdrucks in einen Automaten

Wir nehmen an, dass wir als Eingabe einen regulären Ausdruck R haben. Aus dem vorigen Teil über reguläre Ausdrücke wissen wir, dass ein regulärer Ausdruck insgesamt sechs verschiedene Formen haben kann. Wir unterscheiden also sechs Fälle:

1. R = a für ein Symbol a ∈ Σ. Der reguläre Ausdruck ist also nur ein einziges Symbol aus dem Alphabet Σ, über dem wir arbeiten. Ein Automat, der ein einzelnes Symbol a akzeptiert, sähe so aus:

   

2. R = ϵ, das leere Wort. Ein Automat, der das leere Wort akzeptiert, sähe so aus:

   

3. R = ∅, ein regulärer Ausdruck, der die leere Sprache beschreibt. Ein Automat, der eine solche Sprache erkennt, ist dieser:

   

4. R = R₁ ∪ R₂, wobei R₁, R₂ reguläre Ausdrücke sind. Wir wissen schon, dass die Vereinigung regulärer Sprachen wieder eine reguläre Sprache ist und dass wir einen Automaten bauen können, der eine solche Sprache akzeptiert. Mit anderen Worten: Wir nehmen an, dass wir Automaten haben, die die von den Ausdrücken R₁ und R₂ beschriebenen Sprachen erkennen, und bauen daraus einen Automaten, der die vom Ausdruck R₁ ∪ R₂ beschriebene Sprache akzeptiert. Beispiel: Wenn R₁ = a und R₂ = ϵ, erhalten wir nach dem Verfahren diesen Automaten:

   

5. R = R₁ ∘ R₂, wobei R₁, R₂ reguläre Ausdrücke sind. Derselbe Fall wie im vorigen Punkt. Die Konkatenation regulärer Sprachen ist eine reguläre Sprache, und wir können also einen Automaten bauen, der eine solche Sprache akzeptiert. Wenn also R₁ = a, R₂ = b, sähe die Konkatenation so aus:

   

6. $R=(R_1^{\ast })$, wobei R₁ ein regulärer Ausdruck ist. Wir wissen wieder, dass der Kleene-Stern einer regulären Sprache eine reguläre Sprache ist. Wenn also R = a^∗, sähe der Automat so aus:

   

Durch schrittweises Anwenden dieser Punkte wandeln wir den gesamten regulären Ausdruck in einen endlichen Automaten um.

Ein vollständiges Beispiel

Wir versuchen, den regulären Ausdruck (a|bc)^∗ umzuwandeln. Schrittweise erhalten wir diese Automaten:

Dieser resultierende Automat akzeptiert die Sprache, die der reguläre Ausdruck (a|bc)^∗ beschreibt. Natürlich ist der Automat wahnsinnig kompliziert, und es gibt sicher einen viel einfacheren Automaten, der dieselbe Sprache akzeptiert. Wir können den Algorithmus zur Umwandlung eines NEA in einen DEA verwenden und anschließend die Minimierung des Automaten durchführen.

Quellen

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools