Eine kurze Beschreibung der NFA DFA Umwandlung?

Question

Kann jemand viel heller als ich beschreiben kurz und bündig auf die SO-Community der NFA DFA Konvertierungsalgorithmus? (Vorzugsweise in 500 Worten oder weniger.) Ich habe Diagramme und Vorträge gesehen, die nur dazu gedient haben, zu verwirren, was ich dachte, ich kenne einmal. Ich bin meistens zuversichtlich, eine anfängliche NFA Übergangstabelle aus einem Zustandsdiagramm bei der Erzeugung, sondern danach, verliere ich die DFA in den Epsilons und Untergruppen.

1) In einem Übergang (delta) Tabelle, die die neuen Spalte DFA Staaten darstellt? Ist es die erste Spalte der erzeugten Zustände?

2) In Zeile {2,3}, Spalte 0 von meinem Beispiel unten, was bedeutet die {2,3} bedeutet über die NFA in Bezug auf seine Zustandsdiagramm? (Sorry, ich muss in Bildern denken.) Und ich nehme an, es wird in der DFA ein "Loop-Back auf Eingang 0" sein?

3) Eine einfache „Faustregeln“ auf der Tabelle mit dem DFA bekommen oder auf die Zustände des resultierenden DFA akzeptieren erkennen?

endlich Autonome

delta  |  0    |  1     |
=======+=======+========+
{1}    |{1}    |{2}     |
{2}    |{3}    |{2,3}   |
{3}    |{2}    |{2,4}   |
{2,3}  |{2,3}  |{2,3,4} |
{2,4}  |{3,4}  |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4}  |{2,4}  |{2,4}   |

---

Edit: Hier ist die obige Tabelle in dot Format , prost Regexident <. / p>

digraph dfa {
    rankdir = LR;
    size = "8,5"
/*  node [shape = doublecircle]; "1";*/
    node [shape = circle];

    "1" -> "1" [ label = "0" ];
    "1" -> "2" [ label = "1" ];

    "2" -> "3"   [ label = "0" ];
    "2" -> "2_3" [ label = "1" ];

    "3" -> "2"   [ label = "0" ];
    "3" -> "2_4" [ label = "1" ];

    "2_3" -> "2_3"   [ label = "0" ];
    "2_3" -> "2_3_4" [ label = "1" ];

    "2_4" -> "2_3"   [ label = "0" ];
    "2_4" -> "2_3_4" [ label = "1" ];

    "2_3_4" -> "2_3_4" [ label = "0" ];
    "2_3_4" -> "2_3_4" [ label = "1" ];
    "3_4" -> "2_4" [ label = "0" ];
    "3_4" -> "2_4" [ label = "1" ];
}

Und hier in übertragener Form:

. Hinweis: In der Tabelle fehlt jegliche Informationen über staatliche Akzeptanz, damit so auch die Grafik

Answer 1

Wenn Sie eine DFA von einem NFA konstruieren finden Sie im Grunde jene Sätze von Staaten, dass die NFA in einer Zeit sein kann (wie die NFA simuliert). Zuerst mit dem Startzustand beginnen und dann alle Staaten finden, die durch epsilon Übergänge erreicht werden kann. Dieser Satz von Staaten bildet den Startzustand des resultierenden DFA. Dann folgen Sie den ausgehenden Übergänge von diesem Zustand gesetzt. Diese können zu einem anderen NFA-Zustand führen, für die Sie die Zustände finden erreichbar durch epsilon Eingänge wieder, und Sie erhalten einen weiteren Satz von NFA-Zuständen erhalten, dass ein neuer DFA-Zustand sein wird. Sie tun diesen Vorgang, bis Sie fertig sind.

Der Punkt ist, dass die resultierenden DFA Staaten Sätze der alten NFA-Zustände werden wird, die kompatibel sind (in Bezug auf Epsilon Transitionen). Diese Sätze können auch überlappen, dass kein Fehler ist. Und jetzt kann ich Ihre Fragen beantworten:

1) Die erste Spalte stellt die neuen DFA-Staaten. Es zeigt die NFA-Zustand setzt, die den gegebenen DFA-Zustand bilden.

2) Ihre Annahme richtig ist, bedeutet es, Loopback Zustand {2,3} auf 0 Eingang.

3) Die DFA-Tabelle kann leicht aus dieser Tabelle aufgebaut sein, nennt nur Ihre Zustände mit Buchstaben. Irgendwelche DFA Staaten, die mindestens einen NFA enthalten akzeptieren Staat wird in der DFA akzeptieren Staaten werden auch.

Ich hoffe, ich war klar genug.

Answer 2

Die Kernidee ist wohl zu verstehen, dass die DFA ist eine Art Maschine, die über die NFA überlagert wird. Während die NFA einfacher in Bezug auf die Anzahl von Knoten ist, oder ihre Beziehung mit dem Problem, sind es die Regeln sehr subtil und compled (es geht in die rechts Zustand, was auch immer das sein mag). Die DFA ist viel komplexer in Bezug auf den Knoten enthält, hat aber wirklich einfache Regeln, da es genau einen Ausgangszustand für einen bestimmten Eingang ist.

Die Transformation ist ziemlich straitforward. Jeder Zustand in der DFA ist eine Teilmenge der Zustände im NFA. Der Startzustand der DFA ist der Satz nur den Startzustand des NFA enthält, und die Annahmezustand für die DFA alle seiner Zustände ist, die den Zustand des akzeptieren NFA als Elemente aufweisen.

Die Übergänge in der DFA sind die einzige knifflige Partei. ein NFA ist nicht deterministisch, weil seine Ausgangszustände für eine gegebene Eingabe eine Reihe von Staaten, aber die DFA hat Sätze der entsprechenden NFA-Zuständen, wie seine eigenen Staaten, darstellen, welche der NFA stellt der Automat könnte sein. So ist der Ausgangszustand eines DFA-Zustand für einen bestimmten Eingang ist der Vereinigung der Ausgangszustände aller NFA Staaten dieser DFA-Zustand.

Im Hinblick auf die tatsächlichen Implementierungen hat das EDA einen Zustand Bevölkerung, die im Wesentlichen die Powerset der Staaten der NFA ist. IE, 2 ^ (n) für n NFA Staaten. In der Praxis ist es in der Regel viel kleiner, aber es gibt keine allgemeine Art und Weise seine Größe vorherzusagen, so dass einige praktische NFA zu DFA-Implementierungen der DFA heißt es dynamisch zu generieren, wie sie erreicht werden und Cache ihnen. Sobald eine bestimmte Anzahl von Staaten erstellt werden, verwenden die am wenigsten vor kurzem verworfen wird, um die Größe des Cache-Speichers zu begrenzen.