Nichtdeterministische endliche Automaten (NEA)

Definition

$A=(Q,\Sigma ,q_s,△,F)$

• Q eine endliche Menge von Zuständen ist
• $\Sigma$ ein Eingabealphabet ist
• $q_s\in Q$ der Anfangszustand ist
• $△:Q\times \Sigma \times Q$ die Übergangsrelation ist
• $F\in Q$ eine Menge von akzeptierenden Zuständen ist

siehe DEA