Deterministischer endlicher Automat
Der endliche Automat kann in zwei Typen eingeteilt werden -
- Deterministischer endlicher Automat (DFA)
- Nicht deterministischer endlicher Automat (NDFA / NFA)
Deterministischer endlicher Automat (DFA)
In DFA kann für jedes Eingabesymbol der Zustand bestimmt werden, in den sich die Maschine bewegt. Daher heißt esDeterministic Automaton. Da es eine endliche Anzahl von Zuständen gibt, wird die Maschine aufgerufenDeterministic Finite Machine oder Deterministic Finite Automaton.
Formale Definition eines DFA
Ein DFA kann durch ein 5-Tupel (Q, ∑, δ, q 0 , F) dargestellt werden, wobei -
Q ist eine endliche Menge von Zuständen.
∑ ist eine endliche Menge von Symbolen, die als Alphabet bezeichnet werden.
δ ist die Übergangsfunktion, wobei δ: Q × ∑ → Q.
q0ist der Anfangszustand, von dem aus eine Eingabe verarbeitet wird (q 0 ∈ Q).
F ist eine Menge von Endzuständen von Q (F ⊆ Q).
Grafische Darstellung eines DFA
Ein DFA wird durch aufgerufene Digraphen dargestellt state diagram.
- Die Eckpunkte repräsentieren die Zustände.
- Die mit einem Eingabealphabet gekennzeichneten Bögen zeigen die Übergänge.
- Der Ausgangszustand wird durch einen leeren einzelnen eingehenden Lichtbogen gekennzeichnet.
- Der Endzustand wird durch Doppelkreise angezeigt.
Beispiel
Ein deterministischer endlicher Automat sei →
- Q = {a, b, c},
- ∑ = {0, 1},
- q 0 = {a},
- F = {c} und
Übergangsfunktion δ wie in der folgenden Tabelle gezeigt -
| Derzeitiger Zustand | Nächster Zustand für Eingang 0 | Nächster Status für Eingabe 1 |
|---|---|---|
| a | ein | b |
| b | c | ein |
| c | b | c |
Die grafische Darstellung wäre wie folgt:
