Stichpunkte

Allgemein
	Ein nichtdeterministischer endlicher Automat (NEA) ist ein endlicher Automat
	bei dem es für den Zustandsübergang mehrere Möglichkeiten gibt
	Sigma
	q_0
	F right)<math> definiert werden
	delta
	Formal kann ein NEA <math>mathcal{A}<math> als 5-Tupel <math>left( Q
	<math>mathcal{P}<math> steht hier wie üblich für die Potenzmenge
	<math>Q cap Sigma = empty<math> Es gibt eine Ãœbergangsfunktion <math>delta : Q times Sigma rightarrow mathcal{P}(Q)<math>
	Hierbei gilt Folgendes: &lt;math&gt;Q&lt;math&gt; ist eine endliche Menge von Zuständen (&lt;math&gt;left| Q right| < infty&lt;math&gt;). &lt;math&gt;Sigma&lt;math&gt; ist das Eingabealphabet. &lt;math&gt;left| Sigma right| < infty&lt;math&gt;
	Eine andere Möglichkeit ist die Angabe einer Übergangsrelation &lt;math&gt;Delta subseteq Q times Sigma times Q&lt;math&gt;
	aber auch fehlen können. &lt;math&gt;q_0 in Q &lt;math&gt; ist der Startzustand. &lt;math&gt;F subseteq Q&lt;math&gt; ist eine (endliche) Menge möglicher akzeptierender Zustände (Finalzustände)
	dass auch mehrere Folgezustände möglich sind
	Der wesentliche Unterschied des NEA zum deterministischen endlichen Automaten (DEA) liegt somit darin
	Wenn der Automat nach Lesen des Eingabewortes &lt;math&gt;w in Sigma^*&lt;math&gt; in einem Zustand aus &lt;math&gt;F&lt;math&gt; hält
	so gehört w zur Sprache &lt;math&gt;Lleft(Aright)&lt;math&gt;. 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
	Grundkurs Theoretische Informatik 3.Auflage
	Kurt-Ulrich Witt
	ISBN 3-89319-181-X Sander/Stucky/Herschel
	Einführung in die Automatentheorie
	ISBN 3-519-02937-5 Gottfried Vossen
	Ullman
	Formale Sprachen und Komplexitätstheorie
	Sprachen
	Berechenbarkeit
	Automaten
	ISBN 3-528-23147-5 [Bearbeiten]
Weblinks
	Beschreibung aus Ganimal (http://rw4.cs.uni-sb.de/~ganimal/GANIFA/page13_g.htm) Artikel zum Themengebiet (http://www.inf.fh-flensburg.de/lang/compbau/index.htm) von Hans Werner Lang Beschreibung (http://www.lrz-muenchen.de/services/schulung/unterlagen/regul/regul-11.html#publish4.1.3.0.0.0) von Helmut Richter en:Nondeterministic finite state machine

Dieser Artikel basiert auf dem Artikel Nichtdeterministischer endlicher Automat 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.