DFA (deterministischer endlicher Automat)

Ein deterministischer endlicher Automat , kurz : DFA (deterministic finite automaton), ist nichts anderes als eine abgespekte Turingmaschine, mit deren Hilfe sich eine reguläre Grammatik erzeugen läßt. Was bedeutet, es läßt sich auch überprüfen, ob ein Wort einer bestimmten regulären Sprache angehört. Ein DFA ist auch ein NFA.

Definition:

<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

Akzeptierte Sprache

<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>

In einem DFA gibt es einen Startzustand und eine nicht leere Menge von Endzuständen. Es ist genau festgelegt, mit welchen Element des Eingabealphabets zu welchem Zustand gelangt. Das heißt, dass man niemals mit einem Element des Eingabealphabets von einem Zustand zu zwei unterschiedlichen Zustanden gelangen kann.

Mehrfachübergang:

<math> \delta^*\ (q,\varepsilon) = q\ </math>
<math> \delta^*\ (q, xa) = \delta ( \delta^*(q,x),a) </math>