Wie beurteilen Sie die Vereinigung von zwei DFA konstruieren?

Question

Hat jemand eine einfache Beschreibung des Algorithmus haben für den Aufbau der Vereinigung von zwei gegebenen DFA? Zum Beispiel, sagen wir zwei DFA über haben {0,1} wobei

{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 habe eine bildliche Lösung in meinem Vortrag Notiz, möchte aber sehen, wie andere es beschreiben würden. Daraus kann ich sehen, dass wir im Wesentlichen „multiplizieren“ diese beiden ursprünglichen Tabellen ihre Zustandswerte unter Verwendung von in einem größeren Übergangstabelle führen. Das EDA kann somit aus der resultierenden Tabelle gezogen werden. Klingt das Recht und sollte diese Arbeit für alle DFA Fälle, oder gibt es etwas, was ich bin fehlt?

Answer 1

Der Schlüssel zu verstehen ist, dass man die beiden DFAs simultan laufen müssen, oder im Allgemeinen haben Sie die Zustände beiden DFAs in der Vereinigung DFA zu erhalten.

Das ist, warum Sie die neuen Staaten für die Vereinigung DFA als direkte Multiplikation der ursprünglichen Zustände zu schaffen haben. Auf diese Weise haben Sie einen Zustand für jede Kombination der Zustände in Original DFAs.

Die Übergangsregeln für die neue DFA kann direkt berechnet werden. Wenn Sie zum Beispiel im Zustand Ab, und Sie erhalten eine 0 am Eingang, wäre der erste DFA in den Zustand B gehen und die zweite in den Zustand b, so die Vereinigung für diesen Eingang nächsten Zustand des EDA wird Bb sein.

Diese Methode funktioniert in jedem Fall, wenn Sie eine Vereinigung von zwei oder mehr DFAs vornehmen müssen. Das resultierende DFA möglicherweise nicht optimal, aber später können Sie es mit jedem Algorithmus Sie wie minimieren.