NFA (nichtdeterministischer endlicher Automat)

<math>N\ = ( Z , \Sigma, \delta, Q_0, E )</math>

<math> Z\ </math> Menge der Zustände

<math> \Sigma\ </math> Menge des Eingabealphabets

<math> \delta\ : Z \times \Sigma \rightarrow P(Z) </math>

<math> Q_0 \in Z\ </math> Menge der Startzustände

<math> E\ \in Z\ </math> Menge der Endzustände

Akzeptierte Sprache

<math> L(M) = { x_1 , ... , x_n \in \Sigma \vert q_1 : q_{i+1} \in \beta( q_i, x_i+1 ) , i = 1, ... , n-1 \in N\ }</math>