Nichtdeterministischer endlicher Automat

Ein nichtdeterministischer endlicher Automat (NEA, engl: NFA=nondeterministic finite automaton) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.

Definition

Formal kann ein NEA ${\mathcal {A}}$ als 5-Tupel $\left(Q,\Sigma ,\Delta ,S,F\right)$ definiert werden. Hierbei gilt Folgendes:

• $Q$ ist eine endliche Menge von Zuständen ($\left|Q\right|<\infty$).
• $\Sigma$ ist das Eingabealphabet, $\left|\Sigma \right|<\infty$.
• $\Delta \subseteq (Q\times \Sigma )\times Q$ ist die Übergangsrelation (oder Transitionsrelation).
• $S\in Q$ ist der Startzustand.
• $F\subseteq Q$ ist eine (endliche) Menge möglicher akzeptierender Zustände (Finalzustände). Wenn der Automat nach Lesen des Eingabewortes $w\in \Sigma ^{*}$ in einem Zustand aus $F$ hält, so gehört $w$ zur Sprache $L\left(A\right)$.

Verhalten

Liest der NEA in einem Zustand $q$ das Eingabesymbol $a$, dann wechselt er nichtdeterministisch in einen Nachfolgezustand, der durch die Übergangsrelation gegeben ist. Der Automat hat also die Wahl zwischen allen Zuständen $p$, für die $(q,a,p)\in \Delta$ gilt.

Gibt es keinen solchen Zustand, bleibt der Automat vorzeitig stehen und verwirft die Eingabe.

Ein Eingabewort $w$ gilt dann als akzeptiert, wenn es eine für $w$ durch $\Delta$ gegebene Folge von Zustandswechseln gibt, bei der der Automat nicht vorzeitig stehen bleibt und der letzte Zustand ein akzeptierender Zustand ist.

Transition als Funktion

Alternativ lassen sich die Übergänge auch durch eine Transitionsfunktion definieren, die dann in eine Menge von Zuständen abbildet:

${\mathcal {A}}=\left(Q,\Sigma ,\delta ,S,F,\right)$ mit $\delta :(Q\times \Sigma )\to {\mathcal {P}}(Q)$

Da die Funktion auch auf die leere Menge abbilden kann, sodass $\delta (q,a)=\varnothing$ gelten kann, ist auch hier ein vorzeitiges Stehenbleiben möglich.

Epsilon-Übergänge

Bei einem NEA ist auch ein Zustandsübergang möglich, ohne dabei ein Eingabezeichen zu verbrauchen. Diese Zustandswechsel werden als lambda-Übergänge oder epsilon-Übergänge bezeichnet und üblicherweise mit einem kleinen griechischen $\lambda$ oder $\epsilon$ gekennzeichnet.

Formal ermöglicht man diese Übergänge, indem man das Eingabealphabet erweitert:

${\mathcal {A}}=\left(Q,\Sigma \cup \{\varepsilon \},\Delta ,S,F\right)$

Mehrere Startzustände

Es ist auch möglich, mehrere Startzustände zu erlauben.

Der Automat ist dann definiert als ${\mathcal {A}}=\left(Q,\Sigma ,\Delta ,S,F\right)$ mit $S\subseteq Q$.

Solche Automaten lassen sich mittels $\varepsilon$-Übergängen in NEAs mit genau einem Startzustand überführen, indem man einen neuen Zustand einführt, von dem aus man die ursprünglichen Startzustände durch $\varepsilon$-Übergänge erreicht.

Eigenschaften

NEAs, DEAs und Typ-3-Grammatiken (vgl. Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs umwandeln.

Der wesentliche Unterschied des NEA zum deterministischen endlichen Automaten (DEA) liegt somit darin, dass auch mehrere Folgezustände möglich sind oder auch ganz fehlen können.

Um einen regulären Ausdruck in einen NEA zu überführen, sind gewisse Regeln zu befolgen, die in genauer erläutert werden. Diesen Vorgang nennt man Induktive Konstruktion oder auch Thompson's Konstruktion.

Siehe auch

• Potenzautomat
• Eindeutiger endlicher Automat

Literatur

• John E. Hopcroft u. Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. ISBN 3-89319-181-X
• Sander/Stucky/Herschel: Automaten, Sprachen, Berechenbarkeit. ISBN 3-519-02937-5
• Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik. 3. Auflage. ISBN 3-528-23147-5

Weblinks

• Artikel zum Themengebiet von Hans Werner Lang