Wie konstruieren Sie die Vereinigung von zwei DFA ' s?

Hat jemand eine einfache Beschreibung des Algorithmus zur Konstruktion der Vereinigung zweier gegebenen DFA ist? Zum Beispiel, sagen wir, wir haben zwei DFA ' s über {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

Habe ich eine daraus resultierende transition Tabelle zeigt die union:

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

Habe ich eine bildliche Lösung in meinem Vorlesungsskript, würde aber gerne sehen, wie andere es beschreiben würdest. Von daher, ich kann sehen, dass wir im wesentlichen "multiplizieren" diese beiden ursprünglichen Tabellen anhand Ihrer Status-Werte resultieren in einer größeren übergangs-Tabelle. Die DFA kann somit gezeichnet von der resultierenden Tabelle. Klingt das nicht Recht, und diese Arbeit sollte für alle DFA-Fällen, oder ist es etwas, was ich bin fehlt?

InformationsquelleAutor Old McStopher | 2010-12-15
  1. 9

    Der Schlüssel ist zu verstehen, dass Sie haben, führen Sie die zwei DFAs gleichzeitig, oder im Allgemeinen, die Sie zu pflegen haben sich die Staaten der beiden DFAs in der union DFA.

    Dass ' s, warum Sie zum erstellen der neuen Mitgliedstaaten für die union DFA als eine direkte Multiplikation der ursprünglichen Staaten. Auf diese Weise haben Sie einen Zustand für jede Kombination der Zustände in original-DFAs.

    Den übergang Regeln für die neue DFA kann direkt berechnet dann. Zum Beispiel, wenn Sie im Staat Ab, und Sie bekommen eine 0 bei der Eingabe der ersten DFA gehen würde, um den Zustand B und der zweite in den Zustand b, so ist die union DFA nächsten Zustand für diesen Eingang wird von Bb.

    Diese Methode funktioniert in jedem Fall, wenn Sie brauchen, um eine Vereinigung von zwei oder mehr DFAs. Der resultierende DFA kann nicht optimal sein, aber später kannst du dann minimieren Sie es mit einem Algorithmus, den Sie mögen.

    • Was ist, wenn Sie einen übergang, der unmöglich ist, in einem der Automaten?
    • Fügen Sie-E - (Fehler -) Zustand für den Automaten, der hat Unmögliche übergang. Dass die Automaten bleiben würden, die Statistiken für den rest der Eingabe-Sequenz. Lassen Sie uns sagen, es ist das erste. Sie hätte dann Aa, Ab, Ba, Bb, Ea, Eb-Staaten in die neuen Automaten.
    • Ich denke, es wäre ähnlich, wenn ein Automat hat nur {0,1} als Eingabe-Symbole, und der andere hat {1,2} als Eingabe-Symbole. Dann hätten wir verlängern die beiden Automaten mit Fehlermeldung angezeigt, die besagt (E für die erste und e für das zweite), wo 1. gehen auf-E, wenn 2 ist der Eingang, und 2. würde gehen, um e Zustand, wenn 0 ist die Eingabe.
    InformationsquelleAutor buc
Schreibe einen Kommentar