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 \exists q_{0}\in Q_{0},q_{1},...,q_{n-1}\in Z\ ,q_{n}\in E:q_{i+1}\in \delta (q_{i},x_{i+1})\ ,\ i=1,...,n-1\} $