Simulation eines nichtdeterministischen Automaten
Wenn wir einen nichtdeterministischen Automaten haben und herausfinden wollen, ob er ein gegebenes Wort akzeptiert, können wir den Automaten in einen deterministischen umwandeln, wir können es irgendwie ausprobieren oder wir können einen Algorithmus verwenden, der die Arbeit des NEA simuliert.
Prinzip des Algorithmus
Das Prinzip zeigen wir anschaulich an einem passenden Beispiel. Nehmen wir diesen Automaten:
Das ist ein nichtdeterministischer endlicher Automat, der irgendeine Sprache akzeptiert. Welche, muss uns jetzt überhaupt nicht interessieren. Wir zeigen, wie die Berechnung eines solchen Automaten für das Eingabewort 11001 aussehen kann. Die Überlegung ist die folgende: Wir verarbeiten ein Symbol des Wortes und schauen, wohin wir dank der mehrfachen Übergänge für dasselbe Symbol überall gehen können. Wir merken uns alle diese Zustände und nehmen im nächsten Schritt an, dass wir „in allen diesen Zuständen gleichzeitig“ sind, und uns interessiert, wohin wir von diesen Zuständen aus weiterkommen.
Wir merken uns also die Menge der Zustände, in denen wir uns befinden können, und den ungelesenen Teil des Wortes. Am Anfang haben wir also das Paar ⟨{q0}, 11001⟩. Wir beginnen im Zustand q0 (Startzustand) und auf der Eingabe steht das Wort 11001. Der Automat sieht so aus, rot und fett ist der Zustand hervorgehoben, in dem wir sind:
Das erste Symbol ist 1, aus dem Zustand q0 gibt es nur einen Übergang für das Symbol 1, also kommen wir in den Zustand q1. Wir merken uns das Paar ⟨{q1}, 1001⟩. Der Automat sieht so aus:
Wir machen weiter. Der ungelesene Teil des Wortes hat die Form 1001, also suchen wir wieder Übergänge für 1. Das sind jetzt zwei – zurück in den Zustand q0 und weiter in den Zustand q3. Wir gehen jetzt in beide Zustände zugleich. Wir merken uns also das Paar ⟨{q0; q3}, 001⟩.
Welche Logik steckt dahinter? Wir wissen, dass es einen Weg gibt, vom Startzustand mit dem Wort 11 sowohl in den Zustand q3 als auch in den Zustand q0 zu kommen. Wir wissen noch nicht, welcher Zweig uns nützlich sein wird, also merken wir uns einfach beide. Wir machen weiter. Auf der Eingabe haben wir das Symbol 0. Jetzt müssen wir sowohl die Übergänge aus q0 als auch die Übergänge aus q3 betrachten. Aus dem Zustand q0 führen Übergänge in die Zustände q1 und q2, aus dem Zustand q3 führt ein Übergang zurück nach q1. Wir nehmen alle diese Zustände hinzu und erhalten das Paar ⟨{q1; q2}, 01⟩:
Wir sind in diesem Schritt aber noch nicht fertig. Wir sehen, dass aus dem Zustand q2 ein ε-Übergang in den Zustand q4 führt. Wir wissen, dass wir über einen ε-Übergang „jederzeit gehen können“, ohne ein weiteres Zeichen zu lesen. Mit anderen Worten – ohne ein weiteres Symbol des Eingabewortes zu lesen, können wir noch in den Zustand q4 wechseln. Wir nehmen also den Zustand q4 zu den Zuständen hinzu, in denen wir uns befinden können: ⟨{q1; q2; q4}, 01⟩. Den Automaten würden wir so einfärben:
Als Nächstes steht auf der Eingabe 0. Wir schauen, wohin wir uns von den drei Zuständen, in denen wir sind, bewegen können. Aus q1 können wir nirgendwohin, weil der Übergang für 0 fehlt. Die Berechnung endet in diesem Zweig. Auch aus dem Zustand q4 kommen wir nirgendwohin. Aus dem Zustand q2 kommen wir zurück in den Zustand q2. Aber weil aus dem Zustand q2 wieder ein ε-Übergang in den Zustand q4 führt, können wir auch in den Zustand q4 gelangen. Aus der Zustandsmenge {q1; q2; q4} können wir also für das Symbol 0 in die Zustandsmenge {q2; q4} gelangen, wir erhalten das Paar ⟨{q2; q4}, 1⟩:
Zum Schluss haben wir auf der Eingabe das Symbol 1. Aus dem Zustand q2 kommen wir nirgendwohin, die Berechnung endet in diesem Zweig. Aus dem Zustand q4 gelangen wir aber in die Zustände q3 und q5. Wir erhalten das Paar ⟨{q3; q5}, ε⟩:
Der Automat hat jetzt das ganze Wort gelesen und „befindet sich“ in zwei Zuständen: q3, q5. Da mindestens einer von ihnen ein Endzustand ist, akzeptiert der Automat das Wort 11001.
Algorithmus
Als Erstes brauchen wir eine Funktion, die als Parameter eine Zustandsmenge bekommt und berechnet, in welche Zustände wir zusätzlich mithilfe von ε-Übergängen gelangen können. Die Eingabe ist also der Automat ⟨Q, Σ, δ, q0, F⟩ und eine Zustandsmenge States, die Ausgabe ist eine Obermenge dieser Zustände, in die man mithilfe von ε-Übergängen gelangen kann. Diese Operation nennen wir die ε-Hülle der Menge States.
Diese Funktion verwenden wir in der Funktion, die die Arbeit des nichtdeterministischen Automaten simuliert. Die Eingabe ist der Automat, das Eingabewort w = w1w2… wn und die Menge der Zustände, in denen sich der Automat gerade befindet. Die Ausgabe ist entweder die Antwort Ja oder Nein, je nachdem, ob der Automat das gegebene Wort akzeptiert oder nicht.
Wenn wir überprüfen wollen, ob der Automat das Wort w akzeptiert, rufen wir die Funktion so auf: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0})).
Quellen
Kapitel: Endlicher Automat, Vollständiger Automat, Nichtdeterministischer endlicher Automat, Simulation eines nichtdeterministischen Automaten, Umwandlung eines NEA in einen DEA
