Nichtdeterministischer endlicher Automat

Grundidee und formale Definition

Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es bei einem Zustandsübergang mehrere gleichwertige Möglichkeiten geben kann. Anders als bei einem deterministischen endlichen Automaten ist also nicht eindeutig festgelegt, welchen Übergang der Automat wählen muss.

Formal wird ein NEA A als Quintupel, also als 5-Tupel, A = (Q, Σ, Δ, S, F) definiert. Dabei ist Q eine endliche, nicht leere Menge von Zuständen mit |Q| < ∞. Σ ist ein endliches, nicht leeres Eingabealphabet mit |Σ| < ∞. Δ ⊆ (Q × Σ) × Q ist die Übergangsrelation oder Transitionsrelation. S ∈ Q ist der Startzustand. F ⊆ Q ist die endliche Menge möglicher akzeptierender Zustände, auch Finalzustände genannt.

Wenn der Automat nach dem Lesen eines Eingabewortes w ∈ Σ* in einem Zustand aus F landet, gehört w zur Sprache L(A), die der Automat erkennt.

Arbeitsweise und Akzeptanz

Liest der NEA in einem Zustand q ein Eingabesymbol a, dann wechselt er nichtdeterministisch in einen Nachfolgezustand. Er kann dabei jeden Zustand p wählen, für den (q, a, p) ∈ Δ gilt. Nichtdeterministisch bedeutet hier: Es können mehrere mögliche nächste Zustände existieren, und keiner ist von vornherein als der einzige richtige festgelegt.

Gibt es für q und a keinen solchen Nachfolgezustand, bleibt der Automat vorzeitig stehen und verwirft die Eingabe.

Ein Eingabewort w wird akzeptiert, wenn es für w mindestens eine durch Δ erlaubte Folge von Zustandswechseln gibt, bei der der Automat nicht vorzeitig stehen bleibt und der letzte Zustand ein akzeptierender Zustand ist. Es reicht also aus, dass ein möglicher Rechenweg erfolgreich endet.

Übergänge als Funktion

Statt mit einer Übergangsrelation kann man die Übergänge auch mit einer Transitionsfunktion beschreiben. Dann lautet die Definition A = (Q, Σ, δ, S, F) mit δ: (Q × Σ) → P(Q).

Dabei ist P(Q) die Potenzmenge von Q, also die Menge aller Teilmengen von Q. Die Funktion δ ordnet einem Zustand q und einem Eingabesymbol a nicht nur einen einzelnen Zustand zu, sondern eine Menge möglicher Folgezustände.

Auch hier kann ein vorzeitiges Stehenbleiben auftreten: Die Funktion darf auf die leere Menge abbilden, also δ(q, a) = ∅. Dann gibt es für diese Situation keinen möglichen Übergang.

Epsilon-Übergänge

Man kann NEAs auch so erweitern, dass Zustandsübergänge möglich sind, ohne dass ein Eingabezeichen gelesen wird. Solche Übergänge heißen ε-Übergänge oder ε-Schritte; ε steht für das leere Wort und wird manchmal auch mit λ bezeichnet. In grafischen Darstellungen erscheinen sie als Kanten mit der Beschriftung ε oder λ und heißen deshalb auch ε-Kanten.

Formal erweitert man dafür die Transitionsrelation zu Δ ⊆ Q × (Σ ∪ {ε}) × Q. Dabei muss sichergestellt sein, dass ε nicht schon im Alphabet Σ enthalten ist, sondern ausschließlich das leere Wort bezeichnet.

NEAs mit ε-Übergängen können nicht mehr Sprachen erkennen als NEAs ohne solche Übergänge. Zu jedem NEA mit ε-Übergängen gibt es also einen äquivalenten NEA ohne ε-Übergänge. Trotzdem können ε-Übergänge Konstruktionen vereinfachen. Beispielsweise kann man aus einem NEA A mit wenig Aufwand einen Automaten A' konstruieren, der die Kleene’sche Hülle der Sprache von A akzeptiert: L(A') = (L(A))*.

Mehrere Startzustände

Es ist auch möglich, einen NEA mit mehreren Startzuständen zu definieren. Dann gilt A = (Q, Σ, Δ, S, F) mit S ⊆ Q statt S ∈ Q.

Solche Automaten lassen sich mithilfe von ε-Übergängen in NEAs mit genau einem Startzustand überführen. Dazu führt man einen neuen Startzustand ein, von dem aus die ursprünglichen Startzustände durch ε-Übergänge erreichbar sind.

Diese Idee kann man verwenden, um aus zwei Automaten A und B einen NEA C zu bauen, dessen Sprache die Vereinigung der beiden Sprachen ist: L(C) = L(A) ∪ L(B). Wenn die Zustandsmengen von A und B disjunkt sind, genügt ein neuer Startzustand, der über ε-Übergänge mit den Startzuständen der beiden Automaten verbunden ist. Die Menge der akzeptierenden Zustände ist dann die Vereinigung der akzeptierenden Zustände beider Automaten.

Wichtige Eigenschaften

NEAs, deterministische endliche Automaten (DEAs) und Typ-3-Grammatiken der Chomsky-Hierarchie beschreiben dieselbe Sprachklasse. Ein NEA kann also dieselben Arten von Sprachen erkennen wie ein DEA.

NEAs lassen sich durch die Potenzmengenkonstruktion in äquivalente DEAs umwandeln. Der wesentliche Unterschied zwischen NEA und DEA besteht darin, dass beim NEA mehrere Folgezustände möglich sein können oder auch ganz fehlen können. Ein DEA ist deshalb keine völlig andere Automatenart, sondern eine Sonderform des NEA.

Reguläre Ausdrücke können nach bestimmten Regeln in NEAs überführt werden. Dieses Verfahren heißt Induktive Konstruktion oder Thompsons Konstruktion.