Umwandlung eines NEA in einen DEA

Wir zeigen, wie man einen nichtdeterministischen Automaten in einen deterministischen Automaten umwandelt. Damit beweisen wir, dass nichtdeterministische und deterministische Automaten gleich mächtig sind.

Grundidee

Gegeben sei ein nichtdeterministischer Automat ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ ohne ε-Übergänge. Wir konstruieren einen deterministischen Automaten ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ so, dass

Q_D ⊆ 2^Q_N
Σ_D = Σ_N
p₀ = {q₀}
F_D = {Q ∈ Q_D ∣ Q ∩ F_N ≠ ∅}

Die Übergangsfunktion δ_D definieren wir folgendermaßen:

$\forall Q \in Q_{D}, a \in Σ_{D} : δ_{D} (Q, a) = ⋃_{q \in Q} δ_{N} (q, a)$

Was bedeutet das? Ein nichtdeterministischer Automat kann sich gleichzeitig in mehreren Zuständen befinden, sodass wir zum Beispiel in die Situation kommen können, dass unser nichtdeterministischer Automat in den Zuständen {q₀; q₁} ist. Durch das Lesen des nächsten Symbols, zum Beispiel 1, können wir in die Zustandsmenge {q₀; q₂; q₃} gelangen. In der deterministischen Version desselben Automaten zeigt sich das so, dass wir zwei Zustände erzeugen, sie {q₀; q₁} und {q₀; q₂; q₃} nennen und zwischen ihnen einen Übergang für das Symbol 1 einführen. Formal kommen wir so von einem Zustand in den anderen, aber dank der Benennung wissen wir, dass wir im nichtdeterministischen Automaten in zwei bzw. in drei Zuständen gelandet wären.

Beispiel

Nehmen wir diesen nichtdeterministischen Automaten:

Um den deterministischen Automaten zu konstruieren, müssen wir vor allem eine neue Übergangsfunktion konstruieren. Dabei hilft uns eine Tabelle, in die wir alle Übergänge eintragen. Am Anfang sieht die Tabelle so aus:

$\begin{array}{ccc} Zustand / Symbol & 0 & 1 \\ {q_{0}} \end{array}$

In der linken Spalte haben wir am Ende des Algorithmus alle Zustände des deterministischen Automaten. Die ausgefüllte Tabelle legt dann die Übergangsfunktion fest. Jetzt tragen wir in die Tabelle ein, in welche Zustände wir gelangen, wenn wir im Zustand {q₀} sind und auf der Eingabe die Symbole 0 und 1 stehen.

$\begin{array}{ccc} Zustand / Symbol & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}; q_{2}} \end{array}$

Aus dem Zustand q₀ führt für das Symbol 0 ein Übergang nur in den Zustand q₁, während für das Symbol 1 Übergänge in die Zustände q₁ und q₂ führen. Jetzt fügen wir der Tabelle zwei neue Zustände hinzu: {q₁} und {q₁; q₂}. Warum? Sobald wir in die Tabelle eine Zustandsmenge eintragen, die wir noch nicht in der linken Spalte haben, fügen wir diese Zustandsmenge dort hinzu.

$\begin{array}{ccc} Zustand / Symbol & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}; q_{2}} \\ {q_{1}} \\ {q_{1}; q_{2}} \end{array}$

und füllen wieder aus. Beim Zustand {q₁; q₂} dürfen wir nicht vergessen, beide Zustände zu prüfen, d. h., wohin wir aus dem Zustand q₁ gelangen, vereinigt mit dem, wohin wir aus dem Zustand q₂ gelangen.

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

…und tragen wieder die Übergänge ein:

$\begin{array}{ccc} Zustand / Symbol & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}; q_{2}} \\ {q_{1}} & {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{3}} \\ {q_{1}; q_{2}} & {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{3}} \\ {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{1}; q_{2}; q_{3}} \\ {q_{0}; q_{3}} & {q_{1}} & {q_{1}; q_{2}} \end{array}$

Die Zustände {q₀; q₁; q₃}, {q₁} und {q₁; q₂} haben wir schon dort, also fügen wir nur den Zustand {q₀; q₁; q₂; q₃} hinzu.

Wir haben keinen neuen Zustand mehr hinzugefügt, also ist die Tabelle ausgefüllt. Jetzt müssen wir nur noch das Diagramm zeichnen. Die Zustände des deterministischen Automaten stehen in der ersten Spalte, die Übergänge für die Symbole 0 und 1 in den weiteren. Jeder Zustand, der irgendeinen Endzustand des ursprünglichen Automaten enthält, ist auch in diesem Automaten ein Endzustand. Das heißt, jeder Zustand, der q₃ enthält, ist ein Endzustand. Der Automat sieht so aus:

Wir können zeigen, dass der Automat wirklich richtig funktioniert. Wir versuchen, das Wort 11001 zu akzeptieren. Im deterministischen Automaten gehen wir den Weg

$q_{0} \to^{1} q_{1}, q_{2} \to^{1} q_{0}, q_{3} \to^{0} q_{1} \to^{0} q_{0}, q_{1}, q_{3} \to^{1} q_{0}, q_{1}, q_{2}, q_{3}$

und der Automat würde das Wort akzeptieren, weil der letzte Zustand {q₀; q₁; q₂; q₃} ein Endzustand ist. Im nichtdeterministischen Automaten würden wir während der Simulation in dieselben Zustände gelangen, d. h., wir würden im Zustand q₀ beginnen und für das Symbol 1 in die Zustände {q₁; q₂} kommen. Das nächste Symbol 1 würde uns in die Zustände {q₀; q₃} bringen usw. für die weiteren Zustände. Am Ende würden wir uns in allen Zuständen {q₀; q₁; q₂; q₃} wiederfinden und der Automat würde das Wort akzeptieren.

Quellen

Kapitel: Endlicher Automat, Vollständiger Automat, Nichtdeterministischer endlicher Automat, Simulation eines nichtdeterministischen Automaten, Umwandlung eines NEA in einen DEA

« Zurück: Simulation eines nichtdeterministischen Automaten

Weiter: Reduktion endlicher Automaten »