Nichtdeterministischer endlicher Automat
aus Wikipedia, der freien Enzyklopädie
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 
als 5-Tupel 
definiert werden. Hierbei gilt Folgendes:
- Q ist eine endliche Menge von Zuständen (
). - Σ ist das Eingabealphabet.
, 
- Es gibt eine Übergangsrelation
. 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. 
ist eine (endliche) Menge möglicher Startzustände.
ist eine (endliche) Menge möglicher akzeptierender Zustände (Finalzustände). Wenn der Automat nach Lesen des Eingabewortes 
in einem Zustand aus F hält, so gehört w zur Sprache 
.
NEAs, DEAs und Typ-3-Grammatiken (vgl. Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs umwandeln.
[Bearbeiten] 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
[Bearbeiten] Weblinks
- Artikel zum Themengebiet von Hans Werner Lang
- Beschreibung von Helmut Richter
