DFA (deterministischer endlicher Automat)

<math>M\ = ( 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 Z </math>

<math> q_0 \in Z\ </math> Startzustand

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

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>