Bekannte Algorithmen, um von einem DFA zu einem regulären Ausdruck zu wechseln

28

Ich habe mich gefragt, ob es einen "besseren" Algorithmus gibt (ich erkläre, in welchem ​​Sinne), der von einem DFA ausgeht Aund einen regulären Ausdruck so konstruiert, dass , als die in dem Buch von Hopcroft und Ullman (1979). Dort werden die Mengen verwendet, um Mengen von Zeichenfolgen darzustellen, die den DFA vom Zustand zum Zustand ohne einen Zustand zu , der höher als nummeriert ist . Diese Konstruktion ist zwar offensichtlich korrekt und sehr nützlich, aber eher technisch.rL(A)=L(r)Rijkqiqjk

Ich schreibe eine Monographie über die Theorie algebraischer Automaten und möchte mein Publikum nicht mit zu vielen technischen Details ablenken (zumindest nicht mit Details, die für die Ergebnisse, die ich zeigen möchte, irrelevant sind), aber ich möchte einschließen der Vollständigkeit halber den Nachweis der Gleichwertigkeit von DFA und regulären Ausdrücken. Ich verwende Glushkov-Automaten, um von einem regulären Ausdruck zu einem DFA zu wechseln. Es schien intuitiver zu sein als -Übergänge, die ich überhaupt nicht definiert habe (wieder, weil ich sie nicht brauche).ε

Welche anderen Algorithmen sind dafür bekannt, von einem DFA zu einem regulären Ausdruck zu wechseln? Ich schätze Einfachheit gegenüber Effizienz (das ist in diesem Fall für mich besser), aber das ist keine Voraussetzung.

Vielen Dank im Voraus für Ihre Hilfe!

Janoma
quelle
1
Es ist kein anderer Algorithmus, aber der -Algorithmus kann algebraisch ausgedrückt werden, indem die k- te Potenz einer Matrix von regulären Ausdrücken in der entsprechenden Algebra verwendet wird. Vielleicht finden Sie dies eleganter / prägnanter. Ich suche eine Referenz. Rijkk
Max
1
Der -Algorithmus ist im Wesentlichen eine Variante des Floyd-Warshall-Algorithmus für das All-pairs-Shortest-Path-Problem. Sie können die Darstellung also anhand der Matrixmultiplikation finden, indem Sie nach diesen Schlüsselwörtern suchen. Rijk
Jan Johannsen
2
Ich stimme zu. Es ist im Grunde ein Floyd-Warshall-Algorithmus. Es kann auch unter Verwendung dynamischer Standardprogrammiertechniken abgeleitet werden (genau wie es Floyd-Warshall kann).
David
Ich bin mir sicher, dass ich eine solche Frage schon einmal beantwortet habe, aber ich kann sie nicht finden.
Raphael
@Max könntest du eine Referenz finden? Ich interessiere mich für die Matrixdarstellung, sie sollte eigentlich für Algebristen ansprechender sein.
Janoma

Antworten:

17

Zwei weitere Konstruktionen: Brzozowski-McCluskey aka state elimination [1] und Gaußsche Elimination in einem Gleichungssystem unter Verwendung von Ardens Lemma. Die beste Quelle hierfür ist wahrscheinlich das Buch von Jacques Sakarovitch [2].

[1] J. Brzozowski, E. McCluskey Jr., Signalflussgraphtechniken für sequentielle Schaltungszustandsdiagramme, IEEE Transactions on Electronic Computers EC-12 (1963) 67–76.

[2] J. Sakarovitch, Elemente der Automatentheorie. Cambridge University Press, 2009.

Sylvain
quelle
2
Ich finde den Ansatz, Gleichungen mit Ardens Lemma zu lösen, am einfachsten und am einfachsten zu erklären, deshalb stelle ich ihn in einem Theorie-Einführungskurs so vor.
Jan Johannsen
Die Methode eines Gleichungssystems klingt brillant. Leider hat die Bibliothek meiner Universität das von Ihnen erwähnte Buch (Sakarovitch) nicht, aber ich werde woanders suchen.
Janoma
4
Der Vergleich von Konstruktionen findet sich auch in Sakarovitchs Aufsatz "Die Sprache, der Ausdruck und der (kleine) Automat", CIAA 2005, LNCS 3845, Springer (2006) 15-30. Siehe infres.enst.fr/~jsaka/PUB/Files/LESA.pdf
Hermann Gruber
2
Beachten Sie auch, dass die Reihenfolge, in der die Zustände verarbeitet werden, die Größe des resultierenden regulären Ausdrucks stark beeinflussen kann. Dies gilt immer: ob Sie es mit Ardens Lemma, McNaughton-Yamada, der staatlichen Eliminierung oder einer anderen Variante tun. Es stehen mehrere einfache Heuristiken zur Auswahl einer guten Eliminierungsreihenfolge zur Verfügung.
Hermann Gruber
15

Kozens Buch "Automata & Computability" erwähnt eine elegante Verallgemeinerung dieses Floyd-Warshall-Algorithmus. Da Sie erwähnt haben, dass Sie Algebraisten ansprechen, könnten Sie es nützlich finden. Sie finden es auf Seite 58-59 dieses Textes. (Ich denke, Google Books hat eine Vorschau.)

Grundsätzlich können Sie eine Kleene-Algebra auf Matrizen definieren, deren Einträge aus einer Kleene-Algebra stammen. Die Addition / Vereinigung von Matrizen ist eine koordinatenweise Addition. Die Multiplikation / Verkettung von Matrizen entspricht der normalen Matrixmultiplikation. Kleene-Stern für Matrizen ist definiert als:2×2

[abcd]=[(a+bdc)(a+bdc)bd(d+cab)ca(d+cab)]

Sie können sehen, dass, wenn die linke Matrix die Übergangsmatrix eines DFA mit zwei Zuständen ist , der Eintrag der rechten Matrix die Menge der Pfade (beliebiger Länge) von Zustand i zu Zustand j beschreibt .i,jij

Dann wird der Kleene-Stern größerer Matrizen rekursiv definiert: Teilen Sie die Matrix in 4 Quadranten / Submatrizen a , b , c , d mit den Dimensionen m × m , m × ( n - m ) , ( n - m ) × m , und ( n - m ) × ( n - m ) , und wenden Sie die 2 × 2n×na,b,c,dm×mm×(nm)(nm)×m(nm)×(nm)2×2herrsche jetzt oben mit der matrix minors statt "skalarer" einträge. (Analog dazu, wie die regelmäßige Matrixmultiplikation anhand der Regel für rekursiv definiert werden kann .)2×2

Wenn Sie also eine NFA mit Zuständen und die dazugehörige Übergangsmatrix T haben . Dann wird ein Äquivalent regulärer Ausdruck Σ f F ( T * ) s , f , wo s ist der Startzustand. T kann nach obiger Definition rekursiv ausgewertet werden.nTfF(T)s,fsT

Kozen Ansprüche , dass der Fall , in dem man den Matrix-star rekursiv unter Verwendung auszuwerten entspricht den R k i j - Algorithmus.m=1Rijk

Eine weitere Herleitung der Kleene-Algebra-Strukturen über Matrizen findet sich in einem Vollständigkeitssatz für Kleene-Algebren und der Algebra der regelmäßigen Ereignisse von Kozen.

mikero
quelle
12

Das mit Abstand schönste Verfahren, das ich je gesehen habe, ist das von Sylvain erwähnte. Insbesondere scheint es präzisere Ausdrücke zu liefern als andere.

Ich habe dieses Dokument geschrieben , in dem die Methode für Studenten im letzten Sommer erklärt wurde. Es bezieht sich direkt auf eine bestimmte Vorlesung; Die erwähnte Referenz ist eine typische Definition von regulären Ausdrücken. Ein Beweis von Ardens Lemma ist enthalten; eine für die Richtigkeit der Methode fehlt. Wie ich in der Vorlesung erfahren habe, habe ich leider keine Referenz.

Raphael
quelle
Ich bevorzuge auch diesen Beweis. Ich finde es elegant und leicht zu erklären. Auch Ardens Lemma ist nicht schwer. Ich denke, dies wird die Methode sein, die ich in mein Dokument aufnehmen werde.
Janoma
+