Nichtdeterministischer endlicher Automat

Der endliche Automat, den wir in den vorigen Kapiteln kennengelernt haben (wir kürzen ihn mit EA oder DEA ab), war immer deterministisch. Das zeigte sich daran, dass in jedem Moment klar war, was der Automat tut. Jetzt betrachten wir das allgemeinere Konzept der nichtdeterministischen endlichen Automaten (wir kürzen sie mit NEA ab). Bei ihnen können Übergänge existieren, die vom selben Zustand ausgehen und zum selben Symbol gehören.

Beispiel

Sieh dir das folgende Diagramm eines Automaten an:

Was ist daran besonders? Vom Knoten q₀ führen zwei Kanten für das Symbol 0. Wenn wir also versuchen, das Wort 001 zu akzeptieren, scheint der Automat nicht zu wissen, ob er im Zustand q₀ bleiben oder dem Übergang nach q₁ folgen soll. Ein solcher Automat wäre nichtdeterministisch.

Determinismus bedeutet in diesem Sinn, dass in jeder Situation klar ist, was der Automat tut, es gibt keinen Raum für Mehrdeutigkeit. Ein deterministischer Automat hat für jeden Zustand und jedes Symbol nur einen Übergang. Nichtdeterminismus bedeutet Mehrdeutigkeit – aus einem Zustand können für dasselbe Symbol zum Beispiel drei Übergänge führen.

Wie entscheidet sich der Automat also? Ein nichtdeterministischer Automat wählt immer (manchmal sagen wir auch „errät“) den Übergang, der dazu führt, dass er das Wort akzeptiert – falls das möglich ist.

Wenn wir das Wort 001 in den Automaten eingeben, hat er diese Möglichkeiten, mit dem Wort umzugehen:

$$\begin{array}{r}{q}_0\to q_0\to q_0\to q_0\\ q_0\to q_0\to q_1\to q_2\end{array}$$

plus Möglichkeiten, bei denen er das Wort nicht ganz liest. Im ersten Fall blieb er ständig im Zustand q₀, was er sicher darf, die Übergangsregeln erlauben es. Im zweiten Zweig wagte er sich in weitere Zustände und kam schließlich im Zustand q₂ an, der ein Endzustand ist. In diesem Zweig würde der Automat das Wort akzeptieren. Ein nichtdeterministischer Automat wählt automatisch immer den Zweig, in dem er das Wort akzeptiert, falls ein solcher Zweig existiert.

Wie schafft er es, automatisch den „günstigen“ Zweig zu wählen? Wir können uns das so vorstellen, dass der nichtdeterministische Automat alle möglichen Zweige durchläuft, und wenn er einen Zweig findet, in dem er das Wort akzeptiert, dann akzeptiert er das Wort. Wie könnte er alle Zweige durchlaufen? Ganz einfach: In dem Moment, in dem er in einem Zustand ist, aus dem für das aktuelle Symbol n Kanten führen, kopiert sich der Automat n-mal und jede Kopie geht einen anderen Weg. So gehen wir nach und nach alle Möglichkeiten durch.

Baumdarstellung der Berechnung des Automaten

Wir verändern den vorigen Automaten leicht:

Der Nichtdeterminismus bleibt im ersten Zustand. Der vorige Automat akzeptierte alle Wörter, die auf 01 enden. Dieser veränderte Automat akzeptiert alle Wörter, die das Teilwort 01 enthalten. Er akzeptiert also zum Beispiel das Wort 101 oder 0101. Alle Zweige der Berechnung können wir uns leicht mithilfe eines Baums veranschaulichen, z. B. könnte der Baum für das Wort 01010 so aussehen:

Am Anfang sind wir im Startzustand q₀. Auf der Eingabe haben wir das Wort 01010, das erste ungelesene Zeichen ist 0. Aus dem Zustand q₀ führen zwei Übergänge für das Symbol 0, in die Zustände q₀ und q₁. Der Baum hat also in diesem Knoten zwei Kinder: q₀ und q₁. Weiter lesen wir das Symbol 1. Dort gibt es keine Mehrdeutigkeit, wir gehen in die Zustände q₀ und q₂. Als Nächstes lesen wir das Zeichen 0, im linken Zweig entsteht wieder eine Mehrdeutigkeit, wir teilen die Berechnung in zwei weitere Zweige. In einem bleiben wir wieder in q₀ und im anderen gehen wir nach q₁. Und so weiter.

Beachte, dass insgesamt zwei Zweige im Zustand q₂ enden, also in einem Endzustand. Es gibt zwei Zweige der Berechnung, auf denen der Automat das gegebene Wort akzeptieren kann. Dieser Automat würde das Wort 01010 also akzeptieren. Wir können versuchen, einen ähnlichen Baum für das Wort 1000 zu erstellen.

Die Berechnung bleibt entweder im Zustand q₀ oder geht in den Zustand q₁ über, aber von dort kann sie nirgendwohin weiter, weil auf der Eingabe nur noch Nullen stehen und der Zustand q₁ nur einen Übergang für das Symbol 1 hat. Kein Zweig der Berechnung endet in einem Endzustand, also akzeptiert der Automat das Wort 1000 nicht.

ε-Übergänge

In nichtdeterministischen Automaten können wir zusätzlich auch ε-Übergänge verwenden. Das sind Übergänge, die wir ausführen können, egal welches Symbol auf der Eingabe steht, und zwar ohne ein Symbol des Wortes zu lesen. Wie könnten wir einen nichtdeterministischen Automaten aufschreiben, der das leere Wort akzeptiert, alle Wörter, die nur aus Einsen bestehen, und Wörter der Form (10)ⁿ, d. h. 10, 1010, …?

Wir haben den Automaten in zwei „Teilautomaten“ aufgeteilt. Der obere kümmert sich darum, Wörter zu erkennen, die aus Einsen bestehen, der untere kümmert sich um Wörter der Form (10)ⁿ. Wir versuchen, das Wort 111 zu akzeptieren. Der Automat befindet sich am Anfang im Zustand q₀ und hat auf der Eingabe das Wort 111. Da ihm ε-Übergänge zur Verfügung stehen, kann er sich entscheiden, je nachdem, wie es ihm passt, in den Zustand q₁ oder q₂ zu gehen. Wir sehen, dass es ihm passt, in den Zustand q₁ zu gehen. Der Automat geht dorthin. Dabei hat er auf der Eingabe immer noch das Wort 111! Erst jetzt beginnt er, Symbole des Wortes zu lesen und vom Zustand q₁ wieder in q₁ überzugehen, bis er das ganze Wort gelesen hat und es akzeptiert.

Wenn wir versuchen würden, 1010 zu akzeptieren, würde der Automat am Anfang in den Zustand q₂ gehen und erst von dort aus beginnen, die Symbole zu verarbeiten, und würde das Wort wieder akzeptieren.

Beim Wort 1100 könnte der Automat tun, was er will, er hat keine Möglichkeit, ein solches Wort zu akzeptieren.

ε-Übergänge und Nichtdeterminismus erleichtern uns in vielem die Arbeit. Zum Beispiel lässt sich der Beweis, dass die Vereinigung regulärer Sprachen wieder eine reguläre Sprache ist, mit ε-Übergängen viel einfacher aufschreiben als im Fall deterministischer endlicher Automaten. In diesem Beweis hatten wir Beispiele dieser Automaten

und

und außerdem haben wir einen endlichen deterministischen Automaten konstruiert, der die Vereinigung beider Sprachen akzeptierte. Mit ε-Übergängen können wir einen solchen Automaten so aufbauen:

Wir fügen einfach einen neuen Startzustand hinzu, von ihm führen zwei ε-Übergänge zu den ursprünglichen Startzuständen der ursprünglichen Automaten, und das ist alles. Der Automat entscheidet sich nichtdeterministisch, ob er versucht, das Wort mit dem einen oder dem anderen „Teilautomaten“ zu akzeptieren.

Definition des nichtdeterministischen Automaten

Wir haben schon gezeigt, worin sich ein deterministischer und ein nichtdeterministischer endlicher Automat unterscheiden, es bleibt nur noch, das zu formalisieren. Den deterministischen endlichen Automaten haben wir als Fünftupel ⟨Q, Σ, δ, q₀, F⟩ definiert, wobei Q die Menge der Zustände ist, Σ das Alphabet, δ die Übergangsfunktion, q₀ der Startzustand und F die Menge der Endzustände. Das Einzige, was sich in der Definition der nichtdeterministischen Automaten ändert, ist die Definition der Übergangsfunktion.

In der deterministischen Version konnte die Funktion beim Aufruf δ(q, w) nur einen Zustand zurückgeben, während sie in der nichtdeterministischen Version mehrere Zustände zurückgeben kann – wenn für ein Symbol mehrere Übergänge definiert sind. Weil wir auch ε-Übergänge definieren müssen, bezeichnen wir die Menge Σ ∪ {ε} als Menge Σ_ε, d. h. Σ_ε = Σ ∪ {ε}. Die Funktion δ definieren wir also als

$$\delta :Q\times {\mathrm{\Sigma }}_{\epsilon }\to 2^Q$$

2^Q bezeichnet die Potenzmenge, die Menge aller Teilmengen der Menge Q. Die Formalisierung der Berechnung ist der bei endlichen Automaten sehr ähnlich. Eine Konfiguration des Automaten ist wieder ein Paar ⟨q, w⟩ ∈ Q × Σ^∗. Der Rechenschritt ↦ ist eine Relation auf der Menge der Konfigurationen, sodass

$$⟨q_i,w_0{w}_1\dots w_n⟩\mapsto ⟨q_j,w_1\dots w_n⟩,$$

genau dann gilt, wenn q_j ∈ δ(q_i, w₀). Genau hier liegt der größte Unterschied. In deterministischen Automaten hatten wir diese Bedingung als q_j = δ(q_i, w₀) aufgeschrieben, weil die Funktion δ immer einen Zustand zurückgab. Die nichtdeterministische Version der Übergangsfunktion gibt eine Menge von Zuständen zurück, deshalb steht dort das Symbol ∈. Die reflexive und transitive Hülle der Relation bezeichnen wir wieder mit ↦ ^∗. Wir sagen, der Automat akzeptiert ein Wort w genau dann, wenn ein q_f ∈ F existiert, sodass

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Quellen

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools