Hat jemand eine einfache Beschreibung des Algorithmus zur Konstruktion der Vereinigung zweier gegebener DFAs? Angenommen, wir haben zwei DFAs über {0,1} wo
%Vor%Ich habe eine resultierende Übergangstabelle, die die Vereinigung als:
zeigt %Vor%Ich habe eine bildhafte Lösung in meinen Vorlesungsunterlagen, würde aber 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?
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 direkte Multiplikation der ursprünglichen Zustände erstellen. Auf diese Weise haben Sie einen Status für jede Kombination der Zustände 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 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 später können Sie ihn mit jedem beliebigen Algorithmus minimieren.
Tags und Links dfa transition union finite-automata