✖

Umwandlung eines Automaten in einen regulären Ausdruck

Kapitoly: Reguläre Ausdrücke, Umwandlung eines regulären Ausdrucks in einen Automaten, Verallgemeinerte NKA, Umwandlung eines Automaten in einen regulären Ausdruck

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

Beschreibung des Algorithmus

Als Eingabe haben wir einen NKA A. Als erstes machen wir ihn zu einem ZNKA. In der zweiten Phase entfernen wir in einem Schritt jeweils einen Zustand, ändern die Übergangsfunktionen korrekt und wiederholen den Vorgang, bis nur noch zwei Zustände übrig bleiben, der Anfangs- und der Endzustand. Zwischen ihnen wird eine Kante verlaufen, die ein regulärer Ausdruck als Label ist, der das Ergebnis des gesamten Algorithmus ist. Die gesamte Prozedur besteht also in erster Linie darin, einen Zustand zu entfernen und dann den Automaten zu reparieren, um einen gleichwertigen Automaten zu erhalten.

Entfernen eines Zustands

Wir können das Entfernen eines einzelnen Zustands anhand eines einfachen Beispiels veranschaulichen. Nehmen wir an, dass ein Teil unseres Automaten wie folgt aussieht:

wobei Ri einige reguläre Ausdrücke sind. Wie würde der Automat aussehen, wenn wir den Zustand qr entfernen würden? Wir können uns vorstellen, dass wir uns im Zustand qi befinden und uns fragen, welche Wörter wir in diesem Abschnitt erzeugen können. Wenn wir vom Zustand qi direkt zum Zustand qj übergehen, sind es alle Wörter, die dem regulären Ausdruck R4 entsprechen.

Wenn wir aber zum Zustand qr gehen, können wir Wörter der Form R1 erzeugen. Aber im Zustand qr können wir nach dem regulären Ausdruck R2 suchen, so dass wir tatsächlich Wörter der Form $R_1\circ(R_2^\ast)$ erzeugen können. Nun, da wir immer noch vom Zustand qr zum Zustand qj gelangen können, können wir den regulären Ausdruck R3 hinzufügen. Insgesamt können wir auf diese Weise Wörter der Form $R_1\circ(R_2^\ast)\circ R_3$ erhalten.

Nun wissen wir, dass dieser Teil des Automaten Wörter der Form R4 oder der Form $R_1\circ(R_2^\ast)\circ R_3$ erzeugen kann. Natürlich können wir dies in Form eines regulären Ausdrucks wie $(R_4)|(R_1\circ(R_2^\ast)\circ R_3)$ schreiben.

Nun können wir einfach den Zustand qr entfernen und nur die beiden Zustände qi und qj übrig lassen und den eben berechneten regulären Ausdruck anstelle von R4 schreiben:

Wir tun dies mit jeder Kante von jedem Zustand qi zu irgendeinem Zustand qj und einschließlich Schleifen, d.h. einschließlich des Falles, in dem qi = qj.

Nachdem wir einen Zustand entfernt haben, erhalten wir einen äquivalenten Automaten - einen Automaten, der die gleiche Sprache erkennt.

Der gesamte Algorithmus

Als Eingabe haben wir NKA $A=\left<Q, \Sigma, \delta, q_0, F\right>$.

  1. Wir wandeln NKA A in ZNKA $Z=\left<Q^\prime, \Sigma, \delta^\prime, q_0^\prime, q_f^\prime\right>$ um. Anschließend verwenden wir den Buchstaben k, um die Anzahl der Zustände in Z zu bezeichnen.
  2. Wenn k = 2, wird der Algorithmus beendet und die Kante zwischen dem Anfangs- und Endzustand ist der resultierende reguläre Ausdruck.
  3. Wenn k>2, wählen wir jeden Zustand qr aus, der sich vom Anfangs- und Endzustand unterscheidet, d.h. $q_r\ne q_0^\prime$ und $q_r\ne q_f^\prime$. Als Nächstes erstellen wir eine neue ZNKA $Z^\prime=\left<Q^{\prime\prime}, \Sigma, \delta^{\prime\prime},q_0^{\prime},q_f^{\prime}\right>$, für die sie gültig sein wird: $$ Q^{\prime\prime}=Q^\prime\setminus\left\{q_r\right} $$ und für alle $q_i\in Q^{\prime\prime}\setminus\left\{q_f^\prime\right\}$ und für alle $q_j\in Q^{\prime\prime}\setminus \left\{q_0^\prime\right\}$ sei $$ \delta^{\prime\prime}(q_i, q_j)=(R_4)|(R_1(R_2^\ast)R_3), $$ wobei $R_1=\delta^\prime(q_i,q_r)$, $R_2=\delta^\prime(q_r,q_r)$, $R_3=\delta^\prime(q_r, q_j)$, $R_4=\delta^\prime(q_i, q_j)$. Fahren Sie mit Schritt 2 fort.

Beispiel

Betrachten wir den folgenden endlichen Automaten als Eingabe:

Zuerst wandeln wir ihn in ZNKA um (wir werden keine unnötigen ∅-Übergänge zeigen):

Nun wenden wir den zweiten Teil des Algorithmus an und entfernen einen Knoten. Wir beginnen mit dem Knoten q2. Wir entfernen den Knoten q2 und fügen einen Übergang vom Zustand q1 zum Zustand qf hinzu. Wir bezeichnen diesen Übergang als $b(a|b)^\ast$, denn vom Knoten q1 gelangen wir für Wörter der Form b in den Zustand q2, dann können wir für a|b zyklisch vorgehen und erhalten so $(a|b)^\ast$, und schließlich bewegen wir uns mit Hilfe der Epsilon-Regel zu qf. Auf diese Weise erhalten wir $b(a|b)^\ast\epsilon=b(a|b)^\ast$. Wir erhalten einen Automaten:

Wir entfernen den letzten Zustand, q1, und fügen eine Kante vom Zustand qs zum Zustand qf hinzu. Wie markieren wir sie? Wir können über die Epsilon-Regel zum Zustand q1 gelangen, den wir einfach weglassen können. Dann können wir für a zyklisch vorgehen, so dass wir den regulären Ausdruck $a^\ast$ erhalten. Schließlich gelangen wir über die Kante zu qf, also verketten wir den Ausdruck mit $b(a|b)^\ast$. Also beschreiben wir die Kante mit dem regulären Ausdruck $a^\ast b(a|b)^\ast$.

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

Hilfsmittel