DFA (deterministischer endlicher Automat): Unterschied zwischen den Versionen

Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen
Zeile 1: Zeile 1:
 
[[Kategorie:Automaten und formale Sprachen]]
 
[[Kategorie:Automaten und formale Sprachen]]
 +
 +
 +
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.
  
 
<math>M\ = ( Z , \Sigma, \delta, q_0, E )</math>
 
<math>M\ = ( Z , \Sigma, \delta, q_0, E )</math>

Version vom 25. März 2008, 04:20 Uhr


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.

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