Nichtdysenterische

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, S, F \right)$ definiert werden. Hierbei gilt Folgendes:

$Q$ ist eine endliche Menge von Zuständen ( $\left| Q \right| < \infty$ ).
$Σ$ ist das Eingabealphabet. $\left| \Sigma \right| < \infty$ , $Q \cap \Sigma = \empty$
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.
$S \subseteq Q$ ist eine (endliche) Menge möglicher Startzustände.
$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 Potenzmengenkonstruktionin ä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 Themengebietvon Hans Werner Lang
Beschreibungvon Helmut Richteren:Nondeterministic finite state machine

he:?????? ???? ?? ?????????? ja:???????????? pl:Niedeterministyczny automat sko?czony

Von "http://de.wikipedia.org/Nichtdeterministischer_endlicher_Automat"

Seitenkategorien: Automatentheorie

Dieser Artikel basiert auf dem Artikel aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation.
In der Wikipedia ist eine Liste der Autoren verfügbar.