✖

Umrechnung von NKA in DKA

Kapitoly: Endlicher Automat, Totaler Automat, Nichtdeterministischer endlicher Automat, NKA-Simulation, Umrechnung von NKA in DKA

Wir zeigen, wie man einen nicht-deterministischen Automaten in einen deterministischen Automaten umwandelt und beweisen, dass die Rechenleistung von nicht-deterministischen Automaten und deterministischen Automaten gleichwertig ist.

Die Grundidee

Betrachten wir einen nichtdeterministischen Automaten $\left<Q_N, \Sigma_N, \delta_N, q_0, F_N\right>$ ohne Epsilon-Übergänge. Wir konstruieren einen deterministischen Automaten $\left<Q_D, \Sigma_D, \delta_D, p_0, F_D\right>$ so, dass

  • QD ⊆ 2QN
  • $\Sigma_D = \Sigma_N$
  • p0 = {q0}
  • FD = {Q ∈ QD,|,Q ∩ FN ≠ ∅}

Wir definieren die Übergangsfunktion δD wie folgt:

$$ \forall Q \in Q_D, a\in\Sigma_D: \delta_D(Q, a) = \bigcup_{q\in Q} \delta_N(q, a) $$

Was bedeutet das? Ein nichtdeterministischer Automat kann sich gleichzeitig in mehreren Zuständen befinden, so dass wir beispielsweise zu einer Situation gelangen können, in der sich unser nichtdeterministischer Automat in den Zuständen {q0, q1} befindet. Durch das Lesen eines anderen Symbols, z. B. 1, können wir zu der Menge der Zustände {q0, q2, q3} gelangen. In der deterministischen Version desselben Automaten manifestiert sich dies, indem wir zwei Zustände erzeugen, sie {q0, q1} und {q0, q2, q3} nennen und einen Übergang zwischen ihnen für das Symbol 1 einführen. Formal gelangen wir so von einem Zustand in den anderen, aber dank der Namensgebung wissen wir, dass wir uns im nicht-deterministischen Automaten in zwei bzw. drei Zuständen befinden würden.

Beispiel

Betrachten wir diesen nichtdeterministischen Automaten:

Um einen deterministischen Automaten zu konstruieren, müssen wir zunächst eine neue Übergangsfunktion konstruieren. Dazu brauchen wir eine Tabelle, in der wir alle Übergänge aufschreiben. Zu Beginn sieht die Tabelle wie folgt aus:

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\} \end{array} $$

In der linken Spalte werden alle Zustände des deterministischen Automaten am Ende des Algorithmus stehen. Die ausgefüllte Tabelle bestimmt dann die Übergangsfunktion. Nun schreiben wir in die Tabelle, in welche Zustände wir gelangen, wenn wir uns in den Zuständen {q0} befinden und die Eingangssymbole 0 und 1 sind.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \end{array} $$

Vom Zustand q0 führt der Übergang für das Symbol 0 nur zum Zustand q1, während er für das Symbol 1 zu den Zuständen q1 und q2 führt. Nun fügen wir der Tabelle zwei neue Zustände hinzu: {q1} und {q1, q2}. Warum? In dem Moment, in dem wir der Tabelle eine Reihe von Zuständen hinzufügen, die wir noch nicht in der linken Spalte haben, fügen wir diese Reihe von Zuständen dort ein.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}\\ \left\{q_1, q_2\right\} \end{array} $$

und füllen sie wieder aus. Für den Zustand {q1, q2} dürfen wir nicht vergessen, beide Zustände zu überprüfen, d. h. den Zustand q1 mit dem Zustand q2 zu vergleichen.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \end{array} $$

Wir haben einige neue Zustände, die wir der Tabelle hinzufügen müssen:

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}\\ \left\{q_0,q_3\right\}\\ \end{array} $$

wieder Übergänge hinzufügen:

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \end{array} $$

Die Zustände {q0, q1, q3}, {q1} und {q1,q2} sind bereits vorhanden, also fügen wir nur den Zustand {q0,q1,q2,q3} hinzu.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \left\{q_0,q_1,q_2,q_3\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \end{array} $$

Wir haben keinen neuen Zustand hinzugefügt, die Tabelle ist also vollständig. Jetzt müssen wir nur noch das Diagramm erstellen. Die Zustände des deterministischen Automaten stehen in der ersten Spalte, die Übergänge für die Symbole 0 und 1 stehen in den anderen Spalten. Jeder Zustand, der einen Endzustand des ursprünglichen Automaten enthält, ist auch ein Endzustand in diesem Automaten. Das heißt, jeder Zustand, der q3 enthält, ist ein Endzustand. Der Automat sieht dann wie folgt aus:

Wir können zeigen, dass der Automat wirklich gut funktioniert. Wenn wir versuchen, das Wort 11001 zu akzeptieren. In einem deterministischen Automaten nehmen wir den Pfad

$$ q_0 \rightarrow^1 q_1, q_2 \rightarrow^1 q_0, q_3 \rightarrow^0 q_1 \rightarrow^0 q_0, q_1, q_3 \rightarrow^1 q_0, q_1, q_2, q_3 $$

und der Automat würde das Wort akzeptieren, weil der letzte Zustand {q0, q1, q2, q3} ein Endzustand ist. In einem nicht-deterministischen Automaten würden wir während der Simulation in dieselben Zustände gelangen, d. h. wir würden im Zustand q0 beginnen und für Symbol 1 in den Zustand {q1, q2} gelangen. Das nächste Symbol 1 würde uns in den Zustand {q0,q3} usw. für die nächsten Zustände bringen. Schließlich würden wir uns in allen Zuständen {q0, q1, q2, q3} befinden und der Automat würde das Wort akzeptieren.

Quellen