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 $\backslash mathcal\{A\}$ als 5-Tupel $\backslash left(\; Q,\; \backslash Sigma,\; \backslash Delta,\; S,\; F\; \backslash right)$ definiert werden. Hierbei gilt Folgendes:

• $Q$ ist eine endliche Menge von Zuständen ().
• $\backslash Sigma$ ist das Eingabealphabet. , $Q\; \backslash cap\; \backslash Sigma\; =\; \backslash varnothing$
• Es gibt eine Übergangsrelation $\backslash Delta\; \backslash subseteq\; Q\; \backslash times\; \backslash Sigma\; \backslash 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.
• $S\; \backslash subseteq\; Q$ ist eine (endliche) Menge möglicher Startzustände.
• $F\; \backslash subseteq\; Q$ ist eine (endliche) Menge möglicher akzeptierender Zustände (Finalzustände). Wenn der Automat nach Lesen des Eingabewortes $w\; \backslash in\; \backslash Sigma^*$ in einem Zustand aus $F$ hält, so gehört w zur Sprache $L\backslash left(A\backslash 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

• Beschreibung aus Ganimal
• Artikel zum Themengebiet von Hans Werner Lang
• Beschreibung von Helmut Richter

Automatentheorie

Nondeterministic finite state machine | אוטומט סופי לא דטרמיניסטי | Automa a stati finiti non deterministico | 非決定性有限オートマトン | Niedeterministyczny automat skończony