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 Möglichkeiten gibt.

Formal kann ein NEA ${\mathcal {A}}$ als 5-Tupel $\left(Q,\Sigma ,\delta ,q_{0},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$ , $Q\cap \Sigma =\emptyset$
Es gibt eine Übergangsfunktion $\delta :Q\times \Sigma \rightarrow {\mathcal {P}}(Q)$ , ${\mathcal {P}}$ steht hier wie üblich für die Potenzmenge. Eine andere Möglichkeit ist die Angabe einer Übergangsrelation $\Delta \subseteq Q\times \Sigma \times Q$ . Der wesentliche Unterschied des NEA zum deterministischen endlichen Automaten (DEA) liegt somit darin, dass auch mehrere Folgezustände möglich sind, aber auch fehlen können.
$q_{0}\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)$ .

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

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