Wie konvertiere ich endliche Automaten in reguläre Ausdrücke?

115

Die Konvertierung regulärer Ausdrücke in (minimale) NFA, die dieselbe Sprache akzeptieren, ist mit Standardalgorithmen, z . B. dem Thompson-Algorithmus, einfach . Die andere Richtung scheint jedoch langweiliger zu sein, und manchmal sind die resultierenden Ausdrücke chaotisch.

Welche Algorithmen gibt es, um NFA in gleichwertige reguläre Ausdrücke umzuwandeln? Gibt es Vorteile hinsichtlich Zeitaufwand oder Ergebnisgröße?

Dies soll eine Referenzfrage sein. Bitte fügen Sie eine allgemeine Beschreibung Ihrer Methode sowie ein nicht triviales Beispiel bei.

Raphael
quelle
2
Beachten Sie eine ähnliche Frage bei cstheory.SE, die wahrscheinlich nicht für unser Publikum geeignet ist.
Raphael
Alle Antworten verwenden formale Techniken, um RE aus DFA zu schreiben. Ich glaube, meine Analysetechnik ist vergleichsweise einfach und objektiv. Ich zeige in meiner Antwort: Was ist die Sprache dieser deterministischen endlichen Automaten? Ich denke, es wäre irgendwann hilfreich. Ja, natürlich benutze ich manchmal selbst die formale Methode (Arden-Theorem), um RE zu schreiben. Diese Frage ist komplex, wie in diesem Beispiel angegeben: Wie schreibe
ich

Antworten:

94

Es gibt verschiedene Methoden, um die Konvertierung von endlichen Automaten in reguläre Ausdrücke durchzuführen. Hier werde ich diejenige beschreiben, die normalerweise in der Schule unterrichtet wird und die sehr visuell ist. Ich glaube, es wird in der Praxis am häufigsten verwendet. Das Schreiben des Algorithmus ist jedoch keine so gute Idee.

Methode zum Entfernen des Zustands

Dieser Algorithmus behandelt den Graphen des Automaten und ist daher für Algorithmen nicht sehr geeignet, da er Graphprimitive wie ... state removal benötigt. Ich werde es mit übergeordneten Primitiven beschreiben.

Die Schlüsselidee

Die Idee ist, reguläre Ausdrücke an Kanten zu berücksichtigen und dann Zwischenzustände zu entfernen, während die Kantenbeschriftungen konsistent bleiben.

Das Hauptmuster lässt sich im Folgenden an Figuren ablesen. Die erste hat Bezeichnungen zwischen , die reguläre Ausdrücke e , f , g , h , i sind, und wir möchten q entfernen .p,q,re,f,g,h,iq

pqr automaton

Nach dem Entfernen setzen wir zusammen (wobei die anderen Kanten zwischen p und r erhalten bleiben , dies wird hier jedoch nicht angezeigt):e,f,g,h,ipr

Bildbeschreibung hier eingeben

Beispiel

Verwenden Sie dasselbe Beispiel wie in Raffaels Antwort :

1-2-3 Automat

wir entfernen nacheinander :q2

1-3 Automat

und dann :q3

1 Automat

dann müssen wir noch einen Stern auf den Ausdruck von bis q 1 anwenden . In diesem Fall ist der Endzustand ebenfalls initial, so dass wir wirklich nur einen Stern hinzufügen müssen:q1q1

(ab+(b+aa)(ba)(a+bb))

Algorithmus

L[i,j]ist der Ausdruck der Sprache von bis q j . Zuerst entfernen wir alle Mehrkanten:qiqj

for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

Nun ist die staatliche Entfernung. Angenommen, wir möchten den Zustand entfernen :qk

remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

star(ε)=εe.ε=e∅+e=e∅.e=∅q i q k q j q kεqiqkqjqk

Nun, wie benutzt man remove(k)? Sie sollten End- oder Anfangszustände nicht leichtfertig entfernen, da Sie sonst Teile der Sprache vermissen.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

Wenn Sie nur einen Endzustand und einen Anfangszustand der :q sqfqs

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

Wenn Sie mehrere Endzustände (oder sogar Anfangszustände) haben, gibt es keine einfache Möglichkeit zum Zusammenführen dieser Zustände außer der Anwendung der transitiven Abschlussmethode. Normalerweise ist dies kein Problem von Hand, aber beim Schreiben des Algorithmus ist dies umständlich. Eine viel einfachere Problemumgehung besteht darin, alle Paare und den Algorithmus im (bereits vom Status entfernten) Diagramm auszuführen, um alle Ausdrücke abzurufen, wobei angenommen wird , dass der einzige Anfangszustand und der einzige Endzustand ist state, dann mache die Vereinigung aller .e s , f s f e s , f(s,f)es,fsfes,f

Dies und die Tatsache, dass dadurch Sprachen dynamischer geändert werden als bei der ersten Methode, machen sie beim Programmieren fehleranfälliger. Ich schlage vor, eine andere Methode zu verwenden.

Nachteile

In diesem Algorithmus gibt es viele Fälle, zum Beispiel, um auszuwählen, welchen Knoten wir entfernen möchten, wie viele Endzustände am Ende vorliegen, ob ein Endzustand auch anfänglich sein kann usw.

Beachten Sie, dass dieser Algorithmus jetzt, da er geschrieben wurde, der Methode der transitiven Schließung sehr ähnlich ist. Lediglich der Kontext der Nutzung ist unterschiedlich. Ich empfehle nicht, den Algorithmus zu implementieren, aber es ist eine gute Idee, die Methode manuell zu verwenden.

jmad
quelle
1
Im Beispiel 2. Bild fehlt nach dem Entfernen von Knoten "2" eine Kante - Schleifenkante (ab) in Knoten A.
Panos Kal.
@ Kabamaru: Behoben. Aber jetzt denke ich, das im 3. Bild sollte es auch sein , und vielleicht auch im letzten regulären Ausdruck. εab
Wandering Logic
Sie können die Algorithmus Arbeit für eine beliebige Anzahl von Anfangs- und Endzustand, indem Sie einen neuen Anfang Zugabe und ein neuen Endzustand und diese auf den ursprünglichen Anfangs- und Endzustand , indem -edges. Entfernen Sie nun alle Originalzustände. Der Ausdruck befindet sich dann an der verbleibenden Kante von bis . Die Konstruktion gibt keine Schleifen bei oder da diese Zustände keine eingehenden bzw. nicht eingehenden haben. ausgehende Kanten. Wenn Sie streng sind, haben sie Beschriftungen, die die leere Menge darstellen. q - ε q + q - q + q -q+qεq+qq+q
Hendrik Jan
1
Es gibt immer noch ein Problem mit dem zweiten Beispiel: Vor der Vereinfachung akzeptieren die Automaten "ba" (1, 3, 1), nach der Vereinfachung jedoch nicht.
wvxvw
50

Methode

Die schönste Methode, die ich gesehen habe, ist eine, die den Automaten als Gleichungssystem von (regulären) Sprachen ausdrückt, die gelöst werden können. Es ist besonders schön, da es prägnantere Ausdrücke liefert als andere Methoden.

Sei eine NFA ohne -Übergänge. Erstellen Sie für jeden Zustand die GleichungA=(Q,Σ,δ,q0,F)εqi

Qi=qiaqjaQj{{ε}, qiF, else

wobei die Menge der Endzustände und bedeutet , es ist ein Übergang von mit markiertem . Wenn Sie als oder lesen (abhängig von der Definition Ihres regulären Ausdrucks), sehen Sie, dass dies eine Gleichung für reguläre Ausdrücke ist.Fqiaqjqiqja+

Zur Lösung des Systems benötigen Sie Assoziativität und Verteilungsfähigkeit von und (String-Verkettung), Kommutativität von und Ardens Lemma ¹:

Lassen reguläre Sprachen mit . Dann,L,U,VΣεU

L=ULVL=UV

Die Lösung ist eine Menge von regulären Ausdrücken , einer für jeden Zustand . beschreibt genau die Wörter, die von akzeptiert werden können, wenn es in gestartet ; daher ist (wenn der Anfangszustand ist) der gewünschte Ausdruck.QiqiQiAqiQ0q0


Beispiel

Der Übersichtlichkeit halber bezeichnen wir Singleton-Mengen nach ihrem Element, dh . Das Beispiel stammt von Georg Zetzsche.a={a}

Betrachten Sie diese NFA:

Beispiel nfa
[ Quelle ]

Das entsprechende Gleichungssystem lautet:

Q0=aQ1bQ2εQ1=bQ0aQ2Q2=aQ0bQ1

Stecken Sie nun die dritte Gleichung in die zweite:

Q1=bQ0a(aQ0bQ1)=abQ1(baa)Q0=(ab)(baa)Q0

Für den letzten Schritt wenden wir Ardens Lemma mit , und . Beachten Sie, dass alle drei Sprachen regulär sind und , sodass wir das Lemma anwenden können. Nun stecken wir dieses Ergebnis in die erste Gleichung:L=Q1U=abV=(baa)Q0εU={ab}

Q0=a(ab)(baa)Q0baQ0bb(ab)(baa)Q0ε=((abb)(ab)(baa)ba)Q0ε=((abb)(ab)(baa)ba)(by Arden's Lemma)

Somit haben wir einen regulären Ausdruck für die Sprache gefunden, die vom obigen Automaten akzeptiert wird, nämlich

((a+bb)(ab)(b+aa)+ba).

Beachten Sie, dass es ziemlich prägnant ist (vergleiche mit dem Ergebnis anderer Methoden), aber nicht eindeutig bestimmt wird. Lösen des Gleichungssystems mit einer anderen Reihenfolge von Manipulationen führt zu einem anderen Äquivalent! - Ausdrücke.


  1. Einen Beweis für Ardens Lemma finden Sie hier .
Raphael
quelle
1
Was ist die zeitliche Komplexität dieses Algorithmus? Gibt es eine Grenze für die Größe des produzierten Ausdrucks?
jmite
@jmite: Ich habe keine Ahnung. Ich glaube nicht, dass ich versuchen würde, dies zu implementieren (andere Methoden scheinen in dieser Hinsicht praktikabler zu sein), aber ich verwende sie als Stift-Papier-Methode.
Raphael
1
Hier ist eine Prolog-Implementierung dieses Algorithmus: github.com/wvxvw/intro-to-automata-theory/blob/master/automata/… aber sein maybe_union/2Prädikat könnte mehr Arbeit gebrauchen (insbesondere das Entfernen des gemeinsamen Präfixes), um reguläre Ausdrücke ordentlicher zu gestalten. Eine andere Möglichkeit, diese Methode zu verstehen, besteht darin, sie als Übersetzung von Regex in eine rechtslineare Grammatik zu verstehen, wobei Sprachen mit Prolog-ähnlicher Vereinheitlichung oder ML-ähnlicher Musterübereinstimmung für sehr gute Wandler sorgen und nicht nur Stift und Papier sind Algorithmus :)
wvxvw
Nur eine Frage. Das ε in der ersten Gleichung ist, weil Qo ein Ausgangszustand ist oder weil es ein Endzustand ist? Gleiches gilt, wenn ich zwei Endzustände habe?
Georgio3
@PAOK Überprüfen Sie die Definition von oben (die Linie); es liegt daran, dass ein Endzustand ist. Qiq0
Raphael
28

Brzozowski algebraische Methode

Dies ist die gleiche Methode wie die in Raphaels Antwort beschriebene , jedoch unter dem Gesichtspunkt eines systematischen Algorithmus und dann tatsächlich des Algorithmus. Die Implementierung gestaltet sich einfach und natürlich, sobald Sie wissen, wo Sie anfangen sollen. Es kann auch von Hand einfacher sein, wenn das Zeichnen aller Automaten aus irgendeinem Grund unpraktisch ist.

Wenn Sie einen Algorithmus schreiben, müssen Sie bedenken, dass die Gleichungen immer linear sein müssen, damit Sie eine gute abstrakte Darstellung der Gleichungen erhalten, was Sie beim Lösen von Hand vergessen können.

Die Idee des Algorithmus

Ich werde nicht beschreiben, wie es funktioniert, da es in Raphaels Antwort, die ich vorher lesen möchte, gut gemacht ist. Stattdessen konzentriere ich mich darauf, in welcher Reihenfolge Sie die Gleichungen lösen sollten, ohne zu viele zusätzliche Berechnungen oder zusätzliche Fälle durchzuführen.

Ausgehend von Ardens genialer Lösung zur wir den Automaten als eine Menge von Gleichungen der Form betrachten:X=ABX=AXB

Xi=Bi+Ai,1X1++Ai,nXn

Wir können dies durch Induktion auf lösen, indem wir die Arrays und entsprechend aktualisieren . Im Schritt haben wir:nAi,jBi,jn

Xn=Bn+An,1X1++An,nXn

und Ardens Regel gibt uns:

Xn=An,n(Bn+An,1X1++An,n1Xn1)

und durch Setzen von und wir:Bn=An,nBnAn,i=An,nAn,i

Xn=Bn+An,1X1++An,n1Xn1

und wir können dann alle Bedürfnisse von im System entfernen , indem wir für :Xni,j<n

A ' i , j = A i , j + A i , n A ' n , j

Bi=Bi+Ai,nBn
Ai,j=Ai,j+Ai,nAn,j

Wenn wir mit gelöst haben , erhalten wir eine Gleichung wie folgt: n = 1Xnn=1

X1=B1

ohne . So haben wir unseren regulären Ausdruck bekommen.A1,i

Der Algorithmus

Dank dessen können wir den Algorithmus erstellen. Um die gleiche Konvention wie in der obigen Induktion zu haben, werden wir sagen, dass der Anfangszustand und dass die Anzahl der . Zuerst die Initialisierung zum Füllen von : m Bq1mB

for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[i] := ∅

und :A

for i = 1 to m:
  for j = 1 to m:
    for a in Σ:
      if trans(i, a, j):
        A[i,j] := a
      else:
        A[i,j] := ∅

und dann die Lösung:

for n = m decreasing to 1:
  B[n] := star(A[n,n]) . B[n]
  for j = 1 to n:
    A[n,j] := star(A[n,n]) . A[n,j];
  for i = 1 to n:
    B[i] += A[i,n] . B[n]
    for j = 1 to n:
      A[i,j] += A[i,n] . A[n,j]

Der endgültige Ausdruck lautet dann:

e := B[1]

Implementierung

Auch wenn es ein Gleichungssystem zu sein scheint, das für einen Algorithmus zu symbolisch erscheint, eignet sich dieses System gut für eine Implementierung. Hier ist eine Implementierung dieses Algorithmus in Ocaml (defekter Link) . Beachten Sie, dass bis auf die Funktion brzozowskialles gedruckt oder für Raffaels Beispiel verwendet werden soll. Beachten Sie, dass es eine überraschend effiziente Funktion zur Vereinfachung regulärer Ausdrücke gibt simple_re.

jmad
quelle
4
Link ist tot ...
Columbo
Implementierung in Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
cakraww
24

Transitive Verschlussmethode

Diese Methode ist einfach in Form eines Algorithmus zu schreiben, generiert jedoch absurd große reguläre Ausdrücke und ist unpraktisch, wenn Sie sie von Hand ausführen, meistens, weil dies zu systematisch ist. Es ist jedoch eine gute und einfache Lösung für einen Algorithmus.

Die Schlüsselidee

Ri,jkqiqj{q1,,qk}n

Ri,jqiqjqki,jRi,jqk

Ri,j=Ri,j+Ri,k.Rk,k.Rk,j

RRk1RRk

Beispiel

Wir werden dasselbe Beispiel wie in Raphaels Antwort verwenden . Zunächst können Sie nur die direkten Übergänge verwenden.

aε(ε+a)

R0=[εabbεaabε]

q0q1R0R1

q2q2R2,21=R2,20+R2,10R1,10R1,20=ε+bεa=ε+ba

q2q2q1εq1aεb

R1=[εabbε+baa+bbab+aaε+ab]

R2R3R1,131aR0(+a)aR1((+a)+ε(ε)a)

Algorithmus

Initialisierung:

for i = 1 to n:
  for j = 1 to n:
    if i == j:
      R[i,j,0] := ε
    else:
      R[i,j,0] := ∅
    for a in Σ:
      if trans(i, a, j):
        R[i,j,0] := R[i,j,0] + a

Transitive Schließung:

for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)

qs

e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

()+(a+())(ε)(a+)aa

jmad
quelle