Umwandlung eines Automaten in einen regulären Ausdruck

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

Beschreibung des Algorithmus

Als Eingabe haben wir einen NEA A. Zuerst machen wir daraus einen VNEA. In der zweiten Phase entfernen wir in jedem Schritt einen Zustand, passen die Übergangsfunktion entsprechend an und wiederholen das, bis nur noch zwei Zustände übrig sind – der Start- und der Endzustand. Zwischen ihnen verläuft eine Kante, deren Beschriftung ein regulärer Ausdruck ist, der das Ergebnis des gesamten Algorithmus darstellt. Das ganze Verfahren besteht also vor allem darin, einen Zustand zu entfernen und den Automaten anschließend so zu korrigieren, dass wir einen äquivalenten Automaten erhalten.

Entfernen eines Zustands

Wie man einen Zustand entfernt, können wir an einem einfachen Beispiel darstellen. Nehmen wir an, ein Teil unseres Automaten sieht so aus:

wobei R_i irgendwelche regulären Ausdrücke sind. Wie würde der Automat aussehen, wenn wir den Zustand q_r entfernten? Wir können uns vorstellen, dass wir im Zustand q_i sind und fragen, welche Wörter wir auf diesem Abschnitt alle erzeugen können. Wenn wir vom Zustand q_i direkt in den Zustand q_j gehen, sind es alle Wörter, die dem regulären Ausdruck R₄ entsprechen.

Wenn wir aber in den Zustand q_r gehen, können wir Wörter der Form R₁ erzeugen. Im Zustand q_r können wir aber noch für den regulären Ausdruck R₂ im Kreis laufen, also können wir eigentlich Wörter der Form $R_1\circ (R_2^{\ast })$ erzeugen. Und weil wir vom Zustand q_r noch in den Zustand q_j gelangen können, fügen wir dort noch den regulären Ausdruck R₃ hinzu. Auf diesem Weg können wir insgesamt Wörter der Form $R_1\circ (R_2^{\ast })\circ R_3$ erhalten.

Jetzt wissen wir, dass aus diesem Teil des Automaten Wörter der Form R₄ oder der Form $R_1\circ (R_2^{\ast })\circ R_3$ entstehen können. Das können wir natürlich als regulären Ausdruck in der Form $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$ schreiben.

Nun können wir den Zustand q_r einfach entfernen, nur die zwei Zustände q_i und q_j übrig lassen und anstelle von R₄ den eben berechneten regulären Ausdruck schreiben:

Dieses Verfahren führen wir mit jeder Kante von jedem Zustand q_i in irgendeinen Zustand q_j durch, und zwar einschließlich der Schleifen, d. h. einschließlich des Falls q_i = q_j.

Nach dem Entfernen eines Zustands erhalten wir einen äquivalenten Automaten – einen Automaten, der dieselbe Sprache erkennt.

Der gesamte Algorithmus

Als Eingabe haben wir einen NEA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Wir wandeln den NEA A in einen VNEA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩ um. Mit dem Buchstaben k bezeichnen wir ab jetzt die Anzahl der Zustände in Z.
2. Wenn k = 2, endet der Algorithmus, und auf der Kante zwischen dem Start- und dem Endzustand steht der resultierende reguläre Ausdruck.
3. Wenn k>2, wählen wir einen beliebigen Zustand q_r, der vom Start- und vom Endzustand verschieden ist, d. h. q_r ≠ q₀′ und q_r ≠ q_f′. Weiter erzeugen wir einen neuen VNEA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, für den gilt: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ und für alle q_i ∈ Q′′ ∖ {q_f′} und für alle q_j ∈ Q′′ ∖ {q₀′} sei $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ wobei R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Fahre mit Schritt 2 fort.

Beispiel

Wir haben als Eingabe diesen endlichen Automaten:

Zuerst wandeln wir ihn in einen VNEA um (überflüssige ∅-Übergänge zeichnen wir nicht ein):

Nun wenden wir den zweiten Teil des Algorithmus an und entfernen irgendeinen Knoten. Wir beginnen mit dem Knoten q₂. Wir entfernen den Knoten q₂ und fügen einen Übergang vom Zustand q₁ in den Zustand q_f hinzu. Diesen Übergang beschriften wir mit b(a|b)^∗, denn vom Knoten q₁ gelangen wir für Wörter der Form b in den Zustand q₂, dann können wir für a|b im Kreis laufen, dadurch erhalten wir (a|b)^∗, und schließlich wechseln wir mithilfe der ε-Regel nach q_f. Dabei gilt b(a|b)^∗ϵ = b(a|b)^∗. Wir erhalten den Automaten:

Es bleibt noch, den letzten Zustand q₁ zu entfernen. Wir fügen eine Kante vom Zustand q_s in den Zustand q_f hinzu. Wie beschriften wir sie? In den Zustand q₁ gelangen wir über die ε-Regel, die können wir gleich weglassen. Dann können wir für a im Kreis laufen, also erhalten wir den regulären Ausdruck a^∗. Und schließlich gelangen wir über eine Kante nach q_f, also hängen wir noch b(a|b)^∗ an den Ausdruck an. Die Kante beschriften wir also mit dem regulären Ausdruck a^∗ b(a|b)^∗.

Der Automat hat nur noch zwei Zustände, also endet der Algorithmus. Auf der Kante steht der resultierende reguläre Ausdruck.

Quellen

• Das Beispiel und die Beschreibung des Algorithmus stammen aus M. Sipser: Introduction to the Theory of Computation