Deterministischer endlicher Automat
Ein deterministischer endlicher Automat (DEA) prüft ein Wort Zeichen für Zeichen und hat in jedem Schritt genau einen Folgezustand. Er steckt in Automaten, Eingabeprüfungen und Compilern.
Definition
Ein DEA liest Wörter über einem Alphabet und entscheidet, ob er sie akzeptiert. Er ist ein 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q0, F) }[/math]:
- [math]\displaystyle{ Q }[/math]: endliche, nicht leere Menge der Zustände
- [math]\displaystyle{ \Sigma }[/math]: Eingabealphabet
- [math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math]: Übergangsfunktion
- [math]\displaystyle{ q0 \in Q }[/math]: Startzustand, auch Anfangszustand genannt
- [math]\displaystyle{ F \subseteq Q }[/math]: Menge der Endzustände
Deterministisch bedeutet: Zu jedem Zustand und jedem Zeichen gibt es genau einen Folgezustand [math]\displaystyle{ \delta(q, a) }[/math]. Das Eingabewort legt den Lauf des Automaten damit eindeutig fest.
Die Reihenfolge der Bestandteile im Tupel ist nicht entscheidend, manche Quellen nennen [math]\displaystyle{ \Sigma }[/math] zuerst. Nicht verwechseln: Das Zustandsdiagramm der UML zeichnet ebenfalls Zustände und Übergänge, verwendet aber andere Symbole und beschreibt kein Erkennen von Wörtern.
Darstellungsformen
Ein DEA lässt sich als Übergangsgraph oder als Übergangstabelle darstellen. Beide enthalten dieselben Angaben.
Übergangsgraph
Der Übergangsgraph zeichnet den Automaten als Bild:
- Jeder Zustand ist ein Kreis mit seinem Namen.
- Ein Pfeil mit der Beschriftung „Start“ zeigt auf den Startzustand.
- Jeder Endzustand ist ein Doppelkreis.
- Jeder Übergang [math]\displaystyle{ \delta(p, a) = q }[/math] ist ein Pfeil von [math]\displaystyle{ p }[/math] nach [math]\displaystyle{ q }[/math], beschriftet mit dem Eingabezeichen [math]\displaystyle{ a }[/math]. Führen mehrere Zeichen von [math]\displaystyle{ p }[/math] nach [math]\displaystyle{ q }[/math], steht ein Pfeil mit allen Zeichen, durch Komma getrennt.
Übergangstabelle
Die Übergangstabelle hat für jeden Zustand eine Zeile und für jedes Zeichen des Alphabets eine Spalte. Die Zelle enthält den Folgezustand [math]\displaystyle{ \delta(q, a) }[/math]. Ein Pfeil → vor dem Zustand markiert den Startzustand, ein Stern * die Endzustände. Ist der Startzustand zugleich Endzustand, stehen beide Zeichen davor.
Wortverarbeitung
Der Automat startet im Zustand q0. Jedes Zeichen des Eingabewortes führt genau einen Schritt aus: Aus dem aktuellen Zustand [math]\displaystyle{ q }[/math] und dem gelesenen Zeichen [math]\displaystyle{ a }[/math] ergibt sich der Folgezustand [math]\displaystyle{ \delta(q, a) }[/math]. Die Zustandsfolge dokumentiert den Lauf des Automaten.
Ein Wort wird akzeptiert, wenn der Automat nach dem letzten Zeichen in einem Endzustand steht. Sonst wird es abgelehnt. Das leere Wort [math]\displaystyle{ \varepsilon }[/math] wird akzeptiert, wenn [math]\displaystyle{ q0 \in F }[/math] gilt, denn ohne Zeichen bleibt der Automat im Startzustand.
Die akzeptierte Sprache [math]\displaystyle{ L(A) }[/math] ist die Menge aller Wörter, die der Automat akzeptiert. Sie ist eine formale Sprache über [math]\displaystyle{ \Sigma }[/math].
Vollständiger DEA und Fehlerzustand
Die Übergangsfunktion [math]\displaystyle{ \delta }[/math] braucht für jedes Paar aus Zustand und Zeichen einen Wert. Zeichnungen lassen Übergänge oft weg, nach denen das Wort ohnehin abgelehnt wird. Dann ist der Automat noch nicht vollständig.
Zur Ergänzung führen alle fehlenden Übergänge in einen Fehlerzustand qF. Alle Zeichen bleiben dort in qF. Ein Wort, das einmal in qF gelandet ist, wird nie akzeptiert. qF ist kein Endzustand und nicht mit der Menge [math]\displaystyle{ F }[/math] zu verwechseln.
Minimierung
Zwei Zustände sind äquivalent, wenn sie jedes Restwort gleich entscheiden. Ein Restwort ist der noch ungelesene Teil der Eingabe. Für jedes Restwort endet der Lauf ab dem einen Zustand genau dann in einem Endzustand, wenn der Lauf ab dem anderen Zustand in einem Endzustand endet.
Äquivalente Zustände lassen sich zu einem Zustand zusammenlegen, ohne dass sich die akzeptierte Sprache ändert. Ein Automat ohne äquivalente und ohne nicht erreichbare Zustände ist minimal.
Das Tabellenfüllverfahren findet die äquivalenten Zustände:
- Nicht erreichbare Zustände entfernen.
- Alle Paare aus einem Endzustand und einem Nicht-Endzustand markieren.
- Ein Paar [math]\displaystyle{ (p, q) }[/math] markieren, wenn für ein Zeichen [math]\displaystyle{ a }[/math] das Paar [math]\displaystyle{ (\delta(p, a), \delta(q, a)) }[/math] markiert ist. Das wiederholen, bis nichts Neues hinzukommt.
- Unmarkierte Paare zusammenlegen.
Markierte Paare sind unterscheidbar, unmarkierte Paare sind äquivalent.
Produktautomat
Der Produktautomat lässt zwei DEA über demselben Alphabet gleichzeitig laufen. Seine Zustände sind die Paare [math]\displaystyle{ Q_1 \times Q_2 }[/math] der Zustandsmengen beider Automaten. Der Start besteht aus beiden Startzuständen. Jeder Übergang wird komponentenweise berechnet:
- [math]\displaystyle{ \delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a)) }[/math]
Die Endzustände richten sich nach der gewünschten Sprache:
- Für den Schnitt beider Sprachen gilt [math]\displaystyle{ F = F_1 \times F_2 }[/math]. Beide Komponenten müssen Endzustände sein.
- Für die Vereinigung reicht ein Endzustand in einer der beiden Komponenten.
Beispiele
Kaffeeautomat als vollständigen DEA angeben

Der Kaffeeautomat aus dem Artikel Formale Sprache hat ein Satzfach, das bei genau vier Einheiten voll ist. Ein Kaffee K zählt 1, ein Espresso E zählt 2. Der Zustand merkt sich den Füllstand: q0 bedeutet leer, q1 bis q3 bedeuten 1 bis 3 Einheiten, q4 bedeutet voll. Mehr als vier Einheiten führen in den Fehlerzustand qF (übervoll).
Der DEA [math]\displaystyle{ A = (Q, \Sigma, \delta, q0, F) }[/math] hat diese Bestandteile:
- [math]\displaystyle{ Q = \{q0, q1, q2, q3, q4, qF\} }[/math]
- [math]\displaystyle{ \Sigma = \{K, E\} }[/math]
- [math]\displaystyle{ \delta }[/math] laut Übergangstabelle
- Startzustand q0
- [math]\displaystyle{ F = \{q4\} }[/math]
Die Übergangstabelle hat die Zustände als Zeilen und die Zeichen K und E als Spalten:
| Zustand | K | E |
|---|---|---|
| → q0 | q1 | q2 |
| q1 | q2 | q3 |
| q2 | q3 | q4 |
| q3 | q4 | qF |
| * q4 | qF | qF |
| qF | qF | qF |
Beispiel für das Lesen der Tabelle: Im Zustand q1 führt E nach q3, denn 1 + 2 = 3 Einheiten. Es gilt also [math]\displaystyle{ \delta(q1, E) = q3 }[/math]. Alle Zellen sind gefüllt, der Automat ist vollständig. Er akzeptiert genau die Wörter der Sprache [math]\displaystyle{ L = \{KKKK, EE, EKK, KEK, KKE\} }[/math].
Wortzugehörigkeit mit einem DEA prüfen
Der Automat aus dem vorigen Beispiel prüft drei Wörter. Der Lauf beginnt in q0. Die Schreibweise q0 –K→ q1 bedeutet: Im Zustand q0 wird K gelesen, der Folgezustand ist q1.
KEK: q0 –K→ q1 –E→ q3 –K→ q4
Der Lauf endet in q4. Das ist ein Endzustand, KEK wird akzeptiert.
EEK: q0 –E→ q2 –E→ q4 –K→ qF
Der Lauf endet in qF. Nach EE ist das Satzfach voll, das K lässt es überlaufen. qF ist kein Endzustand, EEK wird abgelehnt.
KK: q0 –K→ q1 –K→ q2
Der Lauf endet in q2. Das ist kein Endzustand, denn das Satzfach hat erst 2 Einheiten. KK wird abgelehnt.
DEA entwerfen
Gesucht ist ein DEA für alle Wörter über [math]\displaystyle{ \Sigma = \{K, E\} }[/math], die das Teilwort KE enthalten. In diesen Wörtern folgt irgendwo ein E direkt auf ein K.
Leitidee: Jeder Zustand merkt sich das Nötige.
- q0: Es ist noch kein Anfang von KE gelesen.
- q1: Das letzte Zeichen war K. Kommt jetzt ein E, ist KE gefunden.
- q2: KE wurde gefunden. Alles Weitere ändert daran nichts, q2 ist der Endzustand.
Daraus ergeben sich die Übergänge:
- In q0 führt K nach q1, denn K kann der Anfang von KE sein. E führt zurück nach q0, denn ein E ohne vorheriges K hilft nicht.
- In q1 bleibt der Automat bei K in q1, denn das neue K ist ein neuer möglicher Anfang. E führt nach q2.
- In q2 führen K und E nach q2.

| Zustand | K | E |
|---|---|---|
| → q0 | q1 | q0 |
| q1 | q1 | q2 |
| * q2 | q2 | q2 |
Jedes Zeichen hat in jedem Zustand einen Folgezustand. Der DEA ist vollständig, ein Fehlerzustand ist nicht nötig.
DEA minimieren

Der DEA vor der Minimierung hat fünf Zustände. Er akzeptiert alle Wörter gerader Länge mit mindestens 2 Zeichen.
| Zustand | K | E |
|---|---|---|
| → q0 | q1 | q2 |
| q1 | q3 | q4 |
| q2 | q4 | q3 |
| * q3 | q1 | q2 |
| * q4 | q2 | q1 |
Schritt 1: Nicht erreichbare Zustände entfernen. Von q0 aus sind alle fünf Zustände erreichbar. Es entfällt keiner.
Schritt 2: Endzustand und Nicht-Endzustand markieren. Die Endzustände sind q3 und q4. Markiert werden die Paare (q0,q3), (q0,q4), (q1,q3), (q1,q4), (q2,q3) und (q2,q4), weil bei jedem dieser Paare genau ein Partner ein Endzustand ist.
Schritt 3: Folgepaare prüfen. Noch unmarkiert sind (q0,q1), (q0,q2), (q1,q2) und (q3,q4).
- (q0,q1) wird markiert: Bei K entsteht das Paar (q1,q3), und dieses ist markiert.
- (q0,q2) wird markiert: Bei K entsteht das Paar (q1,q4), und dieses ist markiert.
- (q1,q2) bleibt unmarkiert: Bei K entsteht (q3,q4), bei E entsteht (q4,q3). Das ist dasselbe Paar, und es ist nicht markiert.
- (q3,q4) bleibt unmarkiert: Bei K entsteht (q1,q2), bei E entsteht (q2,q1). Das ist dasselbe Paar, und es ist nicht markiert.
Eine weitere Runde markiert nichts Neues.
Schritt 4: Unmarkierte Paare zusammenlegen. Aus (q1,q2) und (q3,q4) entstehen die Zustände {q1,q2} und {q3,q4}. q0 bleibt allein.

| Zustand | K | E |
|---|---|---|
| → q0 | {q1,q2} | {q1,q2} |
| {q1,q2} | {q3,q4} | {q3,q4} |
| * {q3,q4} | {q1,q2} | {q1,q2} |
Der minimale DEA hat drei Zustände. Nach dem ersten Zeichen steht er in {q1,q2}, danach wechselt er mit jedem Zeichen zwischen {q1,q2} und {q3,q4}. In {q3,q4} ist die Länge gerade und mindestens 2.
Produktautomat bilden
Gegeben sind zwei DEA über [math]\displaystyle{ \Sigma = \{K, E\} }[/math]:
- DEA 1 „mindestens ein K“ hat die Zustände a und b. a bedeutet, dass noch kein K gelesen wurde, und ist der Startzustand. b bedeutet, dass ein K gelesen wurde, und ist der Endzustand. Bei K wechselt der Automat von a nach b und bleibt dann in b. E ändert nichts.
- DEA 2 „gerade Anzahl E“ hat die Zustände c und d. c bedeutet gerade Anzahl, ist Startzustand und Endzustand. d bedeutet ungerade Anzahl. Bei E wechselt der Automat zwischen c und d. K ändert nichts.
Der Produktautomat soll nur Wörter akzeptieren, die beide Bedingungen erfüllen. Seine Zustände sind die Paare ac, ad, bc und bd, geschrieben ohne Klammern. Der Start ist ac, weil beide Automaten in ihrem Startzustand beginnen. Als Endzustand zählt nur bc, denn nur dort sind beide Komponenten Endzustände: [math]\displaystyle{ F = F_1 \times F_2 = \{bc\} }[/math].

| Zustand | K | E |
|---|---|---|
| → ac | bc | ad |
| ad | bd | ac |
| * bc | bc | bd |
| bd | bd | bc |
Jeder Übergang wird komponentenweise berechnet. Beispiel: Im Zustand ac führt K nach bc, weil a mit K nach b geht und c mit K in c bleibt. E führt nach ad, weil a bei E in a bleibt und c bei E nach d wechselt.
Der Produktautomat akzeptiert die Wörter, die mindestens ein K enthalten und eine gerade Anzahl E haben.