Deterministischer Endlicher Automat
Ein deterministischer endlicher Automat erhält ein Wort als Eingabe und akzeptiert dieses Wort oder nicht.
Die Menge der akzeptierten Wörter bildet die durch den deterministischen endlichen Automaten dargestellte Sprache.
Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, heißen reguläre Sprache.
Zu unterscheiden ist der deterministische endliche Automat vom Nicht-deterministischen endlichen Automaten.
Definition
Ein deterministischer, endlicher Automat wird durch ein 5-Tupel (A, Z, d, q0, E) spezifiziert:
- Das Eingabealphabet A ist eine endliche, nicht leere Menge von Symbolen. Buchstaben des Eingabealphabetes werden in der Regel klein geschrieben.
- Z ist eine endliche, nicht leere Menge von Zuständen Z
- d: Z x A → Z ist die Zustandsübergangsfunktion
- q0 ∈ Z ist der Anfangszustand
- E ⊆ Z ist die Menge der Endzustände
Die Zustandsübergangsfunktion kann durch einen Übergangsgraphen oder durch eine Tabelle dargestellt werden.
Beispiel
Der KGB-Automat:
Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.
- Eingabealphabet: A = {0, 1, ..., 9}
- Zustände: Z = {q0, q1, q2, q3}
- Die Zustandsübergangsfunktion wird durch den Übergangsgraph (rechts) oder die Übergangstabelle (unten) dargestellt.
- Anfangszustand: q0 (im Graph: ein Dreieck)
- Endzustände: {q3} (im Graph: ein Doppelkreis)
Die Zustandsübergangsfunktion als Tabelle dargestellt:
| q0 | q1 | q2 | q3 | |
|---|---|---|---|---|
| q0 | 1..9 | 0 | ||
| q1 | 1..9 | 0 | ||
| q2 | 1..6,8,9 | 0 | 7 | |
| q3 | 0..9 |
Beziehung zu regulären Sprachen und regulären Grammatiken
- Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, heißen reguläre Sprache.
- Zu jedem deterministischen endlichen Automaten gibt es eine reguläre Grammatik.
Diese lässt sich leicht aus dem Übergangsgraphen konstruieren. - Zu jeder regulären Grammatik gibt es einen deterministischen endlichen Automaten.
Dazu erstellt man aus der regulären Grammatik erst einen Nicht-deterministischen endlichen Automaten und aus diesem einen deterministischen endlichen Automaten (mühsam, aber es ist bewiesen, dass das immer geht!)