NFA (nichtdeterministischer endlicher Automat)

$ N\ =(Z,\Sigma ,\delta ,Q_{0},E) $

$ Z\ $ Menge der Zustände

$ \Sigma \ $ Menge des Eingabealphabets

$ \delta \ :Z\times \Sigma \rightarrow P(Z) $

$ Q_{0}\in Z\ $ Menge der Startzustände

$ E\ \in Z\ $ Menge der Endzustände

Akzeptierte Sprache

$ 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\ } $