Nichtdeterministischer endlicher Automat

Der in den vorangegangenen Kapiteln vorgestellteendliche Automat (abgekürzt KA oder DKA) war immer deterministisch, was sich darin äußerte, dass zu jedem Zeitpunkt klar war, was der Automat tun würde. Wir betrachten nun das allgemeinere Konzept der nichtdeterministischen endlichen Automaten (abgekürzt NKA), bei denen es Übergänge geben kann, die vom gleichen Zustand ausgehen und für das gleiche Symbol stehen.

Beispiel

Betrachten Sie das folgende Diagramm eines Automaten:

Was ist das Besondere an ihm? Dass es zwei Kanten gibt, die von dem Knoten q₀ für das Symbol 0 ausgehen. Wenn wir also versuchen, das Wort 001 anzunehmen, scheint es, dass der Automat nicht weiß, ob er im Zustand q₀ bleiben oder dem Übergang zu q₁ folgen soll. Ein solcher Automat wäre nicht-deterministisch.

Determinismus in diesem Sinne bedeutet, dass in jeder Situation klar ist, was der Automat tun wird, es gibt keinen Raum für Zweideutigkeit. Ein deterministischer Automat hat nur einen Übergang für jeden Zustand und jedes Symbol. Nichtdeterminismus bedeutet Mehrdeutigkeit - es kann drei Übergänge von einem Zustand zum selben Symbol geben.

Wie entscheidet der Automat also? Ein nichtdeterministischer Automat wählt (manchmal sagen wir auch "rät") immer den Übergang, der dazu führt, dass er das Wort akzeptiert; wenn möglich.

Wenn wir das Wort 001 in den Automaten eingeben, hat der Automat die folgenden Möglichkeiten, was er mit dem Wort tun soll:

\begin{eqnarray} q_0 \rightarrow q_0 \rightarrow q_0 \rightarrow q_0 \rightarrow q_0 \rightarrow q_1 \rightarrow q_2 \end{eqnarray}

sowie Optionen, bei denen nicht das ganze Wort gelesen wird. Im ersten Fall bleibt er im Zustand q₀, was er natürlich kann, die Übergangsregeln erlauben es. Im zweiten Zweig wagt er sich in andere Zustände und erreicht schließlich den Zustand q₂, der terminal ist. In diesem Zweig würde der Automat das Wort akzeptieren. Ein nicht-deterministischer Automat wird immer automatisch den Zweig wählen, in dem er das Wort akzeptiert, wenn ein solcher Zweig existiert.

Wie wählt er automatisch den "günstigen" Zweig? Wir können uns das so vorstellen, dass ein nicht-deterministischer Automat alle möglichen Verzweigungen durchläuft, und wenn er eine Verzweigung findet, in der er das Wort akzeptiert, dann nimmt er das Wort an. Wie könnte er alle Verzweigungen durchlaufen? Kurz gesagt, in dem Moment, in dem er sich in dem Zustand befindet, von dem aus er für das aktuelle n Kantensymbol ausgeht, kopiert sich der Automat n-einige Male, und jede Kopie nimmt einen anderen Weg. Auf diese Weise werden alle Möglichkeiten der Reihe nach durchgespielt.

Baumdarstellung der Automatenberechnung

Wir modifizieren den vorherigen Automaten leicht:

Der Nicht-Determinismus bleibt im ersten Zustand erhalten. Der vorherige Automat akzeptierte alle Wörter, die auf 01 enden. Dieser modifizierte Automat akzeptiert alle Wörter, die das Teilwort 01 enthalten. Er akzeptiert also zum Beispiel das Wort 101 oder 0101. Wir können alle Verzweigungen der Berechnung leicht mit Hilfe eines Baumes visualisieren, z. B. für das Wort 01010 könnte der Baum wie folgt aussehen:

Zu Beginn befinden wir uns im Ausgangszustand q₀. In der Eingabe haben wir das Wort 01010, das erste ungelesene Zeichen ist 0. Vom Zustand q₀ gibt es zwei Übergänge für das Symbol 0, zu den Zuständen q₀ und q₁. Der Baum wird also zwei Kinder an diesem Knoten haben: q₀ und q₁. Als nächstes lesen wir das Symbol 1. Dort gibt es keine Mehrdeutigkeit, wir gehen zu den Zuständen q₀ und q₂. Als nächstes lesen wir das Symbol 0, wieder gibt es Mehrdeutigkeit im linken Zweig, wir teilen die Berechnung in zwei weitere Zweige auf. In einem bleiben wir wieder bei q₀ und im anderen gehen wir zu q₁. Und so weiter.

Beachten Sie, dass insgesamt zwei Verzweigungen in q₂ enden, dem Endzustand. Es gibt zwei Rechenzweige, da der Automat ein bestimmtes Wort annehmen kann. Dieser Automat würde also das Wort 01010 akzeptieren. Wir können versuchen, einen ähnlichen Baum für das Wort 1000 zu erstellen.

Die Berechnung bleibt entweder im Zustand q₀ oder geht zum Zustand q₁, aber von dort aus kann sie nirgendwo anders hin, weil die Eingabe bereits alle Nullen sind und der Zustand q₁ nur einen Übergang für das Symbol 1 hat. Kein Zweig der Berechnung endet im Endzustand, also akzeptiert der Automat das Wort 1000 nicht.

Epsilon-Übergänge

In nichtdeterministischen Automaten können wir zusätzlich Epsilon-Übergänge verwenden. Das sind Übergänge, die ein beliebiges Symbol auf der Eingabe ausführen können, ohne ein Symbol aus dem Wort zu lesen. Wie könnte man einen nichtdeterministischen Automaten schreiben, der ein leeres Wort, alle Wörter, die nur aus Einsen bestehen, und Wörter der Form 10ⁿ akzeptiert, d. h. 10, 1010, ...?

Wir teilen den Automaten in zwei "Unterautomaten" auf. Der obere kümmert sich um die Erkennung von Wörtern, die aus 1 bestehen, der untere kümmert sich um Wörter der Form 10ⁿ. Versuchen wir, das Wort 111 zu akzeptieren. Der Automat befindet sich zu Beginn im Zustand q₀ und nimmt das Wort 111 als Eingabe an. Da er über Epsilon-Übergänge verfügt, kann er nach eigenem Ermessen in den Zustand q₁ oder q₂ wechseln. Wir sehen, dass es für ihn günstig ist, in den Zustand q₁ zu wechseln. Der Automat wird dorthin gehen. Doch die Eingabe enthält immer noch das Wort 111! Erst an diesem Punkt beginnt er, Symbole aus dem Wort zu lesen und geht vom Zustand q₁ zurück zu q₁, wo er das ganze Wort liest und akzeptiert.

Wenn wir versuchen würden, das Wort 1010 zu akzeptieren, würde der Automat zu Beginn in den Zustand q₂ übergehen und erst von dort aus mit der Verarbeitung der Symbole beginnen und das Wort wieder akzeptieren.

Für das Wort 1100 könnte der Automat alles tun, er hat keine Möglichkeit, ein solches Wort zu akzeptieren.

Epsilon-Übergänge und Nicht-Determinismus erleichtern unsere Arbeit in vielerlei Hinsicht, zum Beispiel kann der Beweis, dass die reguläre Sprachvereinheitlichung wieder eine reguläre Sprache ist, viel eindeutiger in Epsilon-Übergängen geschrieben werden als im Fall von endlichen Automaten. In diesem Beweis hatten wir Beispiele für solche Automaten

a

und wir haben außerdem einen endlichen deterministischen Automaten konstruiert, der die Vereinigung beider Sprachen akzeptiert. Mit Epsilon-Übergängen können wir einen solchen Automaten wie folgt konstruieren:

Kurz gesagt, wir fügen einen neuen Anfangszustand hinzu, von dem zwei Epsilon-Übergänge zu den Anfangszuständen des ursprünglichen Automaten führen, und das war's. Der Automat entscheidet nicht-deterministisch, ob er versucht, das Wort mit dem einen oder dem anderen "Unterautomaten" anzunehmen.

Definition eines nichtdeterministischen Automaten

Wir haben bereits gezeigt, wie sich deterministische und nicht-deterministische endliche Automaten unterscheiden, es geht nur noch darum, dies zu formalisieren. Wir haben einen deterministischen endlichen Automaten als ein Fünffach $\left<Q, \Sigma, \delta, q_0, F\right>$ definiert, wobei Q die Menge der Zustände, $\Sigma$ das Alphabet, δ die Übergangsfunktion, q₀ der Anfangszustand und F die Menge der Endzustände ist. Das Einzige, was sich bei der Definition von nichtdeterministischen Automaten ändert, ist die Definition der Übergangsfunktion.

In der deterministischen Version könnte die Funktion zum Aufruf von δ(q, w) nur einen Zustand zurückgeben, während sie in der nichtdeterministischen Version mehrere Zustände zurückgeben kann - wenn mehrere Übergänge für ein einzelnes Symbol definiert sind. Da wir auch Epsilon-Übergänge definieren müssen, markieren wir die Menge $\Sigma\cup\left\{\varepsilon\right\}$ als die Menge $\Sigma_\varepsilon$, d.h. $\Sigma_\varepsilon=\Sigma\cup\left\{\varepsilon\right\}$. Wir definieren also die Funktion δ als

$$ \delta: Q \times \Sigma_\varepsilon\rightarrow 2^Q $$

Dabei bezeichnet 2^Q die Potenzmenge, also die Menge aller Teilmengen der Menge Q. Die Formalisierung der Berechnung ist derjenigen von endlichen Automaten sehr ähnlich. Die Konfiguration des Automaten ist wieder das Paar $\left<q, w\right> \in Q \times \Sigma^\ast$. Der Schritt der Berechnung von $\mapsto$ ist eine Sitzung auf der Menge der Konfigurationen, so dass

$$ \left<q_i, w_0w_1\dots w_n\right> \mapsto \left<q_j, w_1\dots w_n\right>, $$

genau dann, wenn q_j ∈ δ(q_i, w₀). In diesem Theorem liegt der größte Unterschied. In deterministischen Automaten hatten wir diese Bedingung als q_j = δ(q_i, w₀) geschrieben, weil die Funktion δ immer einen einzigen Zustand zurückgab. Die nicht-deterministische Version der Übergangsfunktion gibt eine Menge von Zuständen zurück, daher das Symbol ∈. Wir werden den reflexiven und transitiven Sitzungsabschluss wieder mit $\mapsto^\ast$ bezeichnen. Wir sagen, dass ein Automat das Wort w nur dann akzeptiert, wenn es q_f ∈ F so gibt, dass

$$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>.$$

Ressourcen

• M. Sipser: Einführung in die Rechentheorie
• Aho, Sethi, Ullman: Compiler: Prinzipien, Techniken und Werkzeuge