Dies ist eine alte Version des Dokuments!
Deterministische endliche Automaten
DEA ist die deutsche Abkürzung für Deterministischer Endlicher Automat. Im Englische lautet die Abkürzung DFA fürDeterministic Final Automaton. Auch in deutschsprachiger Fachliteratur wird oft das Akronym DFA genutzt.
Definition
Eine DEA ist ein 5-Tupel DEA = { Q, Σ, δ, E, s}
er besteht also aus den folgenden 5 Teilen:
Q
Menge aller Zustände (oft auch Z oder S (engl. state))Σ
Alphabet / Menge der Alphabetzeichen (Sigma)δ
Übergangsfunktion (Delta)E
Menge der akzeptierenden Endzustände,s
Startzustand.
Darstellung
Ein DEA wir häufig durch seinen Übergangsgraphen dargestellt.Gelegentlich wird auch der Begriff Zustandsübergangsdiagramm verwendet.
Im Übergangsgraphen sind viele Informationen enthalten:
- Q={q0,q1,q2,q3}
- Σ={a,b}
- δ wird dargestellt durch die Pfeile, die von einem Zustand zum nächsten führen.
- E={q3}
- s=q0
Die Übergangsmatrix
Die Übergangsfunktion δ kann auch als Übergangsmatrix dargestellt werden. Dabei werden in der ersten Spalte alle Zustände eingetragen und in der ersten Zeile alle Zeichen des Eingabealphabets Σ eingetragen. In den Tabellenzellen wird vermerkt, zu welchem Zustand der Automat wechselt, wenn er zuvor im Zustand der ersten Spalte war und dann die Eingabe der ersten Zeile erfolgt.
δ | a | b |
---|---|---|
q0 | q1 | q2 |
q1 | q3 | |
q2 | q3 | |
q3 |