DFA (deterministischer endlicher Automat): Unterschied zwischen den Versionen
| (8 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
[[Kategorie:Automaten und formale Sprachen]] | [[Kategorie:Automaten und formale Sprachen]] | ||
| − | <math> | + | |
| + | 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. | ||
| + | |||
| + | <b>Definition:</b><br/> | ||
| + | |||
| + | <math>M\ = ( Z , \Sigma, \delta, q_0, E )</math> | ||
<br/> | <br/> | ||
| Zeile 10: | Zeile 15: | ||
<math> \delta\ : Z \times \Sigma \rightarrow Z </math> <br/> | <math> \delta\ : Z \times \Sigma \rightarrow Z </math> <br/> | ||
| − | <math> | + | <math> q_0 \in Z\ </math> Startzustand <br/> |
| − | <math> E\ </math> Menge der Endzustände <br/> | + | <math> E\ \in Z\ </math> Menge der Endzustände <br/> |
| + | <b>Akzeptierte Sprache</b> | ||
<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> | <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. | ||
| + | |||
| + | <b>Mehrfachübergang: </b> | ||
| + | |||
| + | <math> \delta^*\ (q,\varepsilon) = q\ </math> <br/> | ||
| + | <math> \delta^*\ (q, xa) = \delta ( \delta^*(q,x),a) </math> | ||
Aktuelle Version vom 2. April 2008, 11:16 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.
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>
