DFA (deterministischer endlicher Automat): Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| (9 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| 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. | |||
<b>Definition:</b><br/> | |||
<math>M\ = ( Z , \Sigma, \delta, q_0, E )</math> | |||
<br/> | |||
<math> Z\ </math> Menge der Zustände <br/> | |||
<math> \Sigma\ </math> Menge des Eingabealphabets <br/> | |||
<math> \delta\ : Z \times \Sigma \rightarrow Z </math> <br/> | |||
<math> q_0 \in Z\ </math> Startzustand <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:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): M\ = ( Z , \Sigma, \delta, q_0, E )
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): Z\
Menge der Zustände
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \Sigma\
Menge des Eingabealphabets
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \delta\ : Z \times \Sigma \rightarrow Z
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): q_0 \in Z\
Startzustand
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): E\ \in Z\
Menge der Endzustände
Akzeptierte Sprache
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): 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} fürFehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \ i = 0, ... , n-1 \}
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:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \delta^*\ (q,\varepsilon) = q\
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \delta^*\ (q, xa) = \delta ( \delta^*(q,x),a)
