Nichtdeterministischer endlicher Automat

Formal kann ein NEA <math>\mathcal{A}</math> als Tupel <math>\left( Q \Sigma \delta q_0 F definiert werden. Hierbei gilt Folgendes:

• <math>Q</math> ist eine endliche Menge von Zuständen Q \right| < \infty</math>). Statt <math>Q</math> wird auch <math>Z</math> verwendet.
• <math>\Sigma</math> ist das Eingabealphabet. <math>\left| \Sigma \right| \infty</math> <math>Q \cap \Sigma = \empty</math>
• Es gibt eine Übergangsfunktion <math>\delta : Q \Sigma \rightarrow \mathcal{P}(Q)</math> (hier liegt der einzige zum deterministischen endlichen Automaten (DEA) <math>\mathcal{P}</math> steht hier wie üblich die Potenzmenge ).
• <math>q_0 \in Q </math> ist der Startzustand. <math>q_0</math> wird oft auch <math>z_0</math> verwendet.
• <math>F \subseteq Q</math> ist eine (endliche) Menge akzeptierender Zustände (= Endzustandsmenge). Der Automat hält wenn er einen akzeptierenden Zustand erreicht. Statt wird oft auch <math>A</math> verwendet.

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

Weblinks

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

Bücher zum Thema Nichtdeterministischer endlicher Automat

Dieser Artikel von Wikipedia unterliegt der GNU FDL.