Wie konstruieren Sie die Vereinigung von zwei DFAs?

Question

Hat jemand eine einfache Beschreibung des Algorithmus zur Konstruktion der Vereinigung von zwei gegebenen DFA? Zum Beispiel, sagen wir zwei DFA über haben {0,1}, wo

{w|w has an odd number of characters} 
    w has states A and B 

delta | 0 | 1 
---------------- 
    A | B | B 
---------------- 
    B | A | A 


{x|x has an even number of 1s} 
    x has states a and b 

delta | 0 | 1 
---------------- 
    a | a | b 
---------------- 
    b | b | a 

Ich habe eine resultierende Übergangstabelle zeigt die Vereinigung als:

delta | 0 | 1 
---------------- 
    Aa | Ba | Bb 
---------------- 
    Ab | Bb | Ba 
---------------- 
    Ba | Aa | Ab 
---------------- 
    Bb | Ab | Aa 

ich eine bildliche Lösung in meinem Skriptum haben, aber würde gerne sehen, wie andere es beschreiben würden. Daraus kann ich sehen, dass wir diese beiden ursprünglichen Tabellen im Wesentlichen "multiplizieren", indem wir ihre Statuswerte verwenden, um eine größere Übergangstabelle zu erhalten. Der DFA kann somit aus der resultierenden Tabelle gezogen werden. Klingt das richtig und sollte das für alle DFA-Fälle funktionieren, oder fehlt mir etwas?

Answer 1

Der Schlüssel zum Verständnis ist, dass Sie die beiden DFAs gleichzeitig ausführen müssen, oder Sie müssen im Allgemeinen die Status beider DFAs in der Union-DFA beibehalten.

Deshalb müssen Sie die neuen Zustände für die Union DFA als eine direkte Multiplikation der ursprünglichen Zustände erstellen. Auf diese Weise haben Sie einen Status für jede Kombination der Status in ursprünglichen DFAs.

Die Übergangsregeln für das neue DFA können dann direkt berechnet werden. Wenn Sie sich beispielsweise im Zustand Ab befinden und eine Eingabe von 0 erhalten, würde der erste DFA in den Zustand B und der zweite in den Zustand b gehen, sodass der nächste Status der Union DFA für diesen Eingang Bb ist.

Diese Methode funktioniert in jedem Fall, wenn Sie zwei oder mehr DFAs zusammenführen müssen. Der resultierende DFA ist möglicherweise nicht optimal, aber Sie können ihn später mit jedem beliebigen Algorithmus minimieren.