Wie überprüfe ich, ob ein DFA einem NFA entspricht?

Ich lerne, wie man NFAs in DFAs konvertiert, und ich möchte sicherstellen, dass ich es richtig mache. Offensichtlich ist es keine Sache, in die andere Richtung zurückzukehren. Kennt jemand einen Algorithmus, um zu überprüfen, ob ein DFA einem NFA entspricht?

Dies ist eine problematische Frage. Es gibt eine Möglichkeit, die Gleichwertigkeit von Automaten zu überprüfen, die ich jetzt erläutern werde, aber ich fürchte, es wird Ihnen nicht helfen, wie Sie am Ende sehen werden.

Denken Sie daran, dass zwei Mengen und gleich sind, wenn und (dies ist die Definition der Mengengleichheit). Es reicht also aus, zu überprüfen, ob und , wobei und Ihr DFA bzw. NFA sind.B A ⊆ B B ⊆ A L ( D ) ⊆ L ( N ) L ( N ) ⊆ L ( D ) D $A$$B$$A\subseteq B$$B\subseteq A$$L(D)\subseteq L(N)$$L(N)\subseteq L(D)$$D$$N$

Aber wie überprüfen Sie die Einschließung von Sprachen, könnten Sie fragen. Nun, beobachten Sie nun, dass iff (wobei das Komplement von ).A ∩ ¯ B = ∅ ¯ B$A\subseteq B$$A\cap \overline{B}=\emptyset$$\overline{B}$$B$

Betrachten wir zunächst, ob . Dazu müssen Sie ergänzen (sehr einfach - die akzeptierenden und ablehnenden Zustände austauschen), dann den Schnittautomaten (z. B. mit der Produktkonstruktion) mit konstruieren und auf Leere prüfen, indem Sie einen Pfad zu einem akzeptierenden Zustand finden.D $L(N)\subseteq L(D)$$D$$N$

Die umgekehrte Richtung zeigt jedoch, warum dies Ihnen nicht hilft. Um zu überprüfen, ob , müssen Sie ergänzen . Um eine NFA zu ergänzen, müssen Sie sie zunächst in eine DFA konvertieren, wodurch die gesamte Idee sinnlos wird.$L(D)\subseteq L(N)$$N$

Im Wesentlichen ist das Problem mit Ihrer Frage viel tiefer: Sie möchten überprüfen, ob Sie (ein undefiniertes Rechenmodell) einen genau definierten Algorithmus ordnungsgemäß ausgeführt haben. Das ist also kein wirkliches Informatikproblem.

Ich werde dies sagen: Nach den von mir vorgeschlagenen Konstruktionen ist es nicht schwer zu schließen, dass wenn es ein Wort mit einer Länge von höchstens ( ist die Anzahl der Zustände von ) das wird von dem einen und nicht vom anderen akzeptiert. Sie können also alle Wörter bis zu dieser Länge ausprobieren.2 2 n n $L(D)\neq L(N)$$2^{2n}$$n$$N$

Eine Möglichkeit besteht darin, den NFA in einen DFA umzuwandeln und dann die Äquivalenz der beiden DFAs zu überprüfen, für die es einen linearen Algorithmus gibt [1].

Das folgende Papier behandelt den allgemeineren Fall der Äquivalenz von zwei NFAs (was natürlich auch für Ihren Fall gilt).

Filippo Bonchi, Damien Pous, Überprüfung der NFA-Äquivalenz mit Bisimulationen bis zur Kongruenz Prinzip der Programmiersprachen (POPL), Januar 2013, Roma, Italien. ACM, S. 457–468, 2013.

Zusammenfassung . Wir führen die Bisimulation bis zur Kongruenz als eine Technik zum Nachweis der Sprachäquivalenz nicht deterministischer endlicher Automaten ein. Unter Ausnutzung dieser Technik entwickeln wir eine Optimierung des klassischen Algorithmus von Hopcroft und Karp [1]. Wir vergleichen unseren Ansatz mit den kürzlich eingeführten Antichain-Algorithmen, indem wir die beiden zugrunde liegenden koinduktiven Beweismethoden analysieren und in Beziehung setzen. Wir geben konkrete Beispiele, bei denen wir uns gegenüber Antichains exponentiell verbessern. experimentelle Ergebnisse zeigen darüber hinaus nicht zu vernachlässigende Verbesserungen.

[1] JE Hopcroft und RM Karp. Ein linearer Algorithmus zum Testen der Äquivalenz endlicher Automaten. TR 114, Cornell Univ., Dezember 1971.

Siehe auch den Web-Anhang zu diesem Dokument , der Coq-Proof-Skripte der Ergebnisse, einen Link zu einer Implementierung und ein interaktives Applet enthält.

Bei dieser Frage geht es eher um angewandte Softwaretests und die Überprüfung der Richtigkeit in der Praxis als um eine theoretische Frage.

• $D_1 \cap \bar{D_2}$$D_2 \cap \bar{D_1}$$\bar{D}$

• Sie können sich auf zuvor getestete Software verlassen, die getestet wurde, um Ihre Ergebnisse zu validieren. zB AT & T FSM Bibliothek

• eine andere Idee: randomisierte Tests. Wähle zufällige Zeichenfolgen in deiner Sprache. Stellen Sie fest, ob die Zeichenfolgen vom DFA / NFA akzeptiert oder nicht akzeptiert werden. Wenn die beiden nicht gleich sind, werden Sie mit hoher Wahrscheinlichkeit Zeichenfolgen finden, die nicht übereinstimmen.

• Eine andere Idee: Sie können Code schreiben, um alle Zweige des DFA und des NFA bis zu einer bestimmten Tiefe zu durchlaufen und nach Fehlanpassungen zu suchen. Dies entspricht der Aufzählung aller potenziell akzeptierten Zeichenfolgen mit bestimmten Längen.