Der deterministische Automat

Ein deterministischer endlicher Automat (DEA) prüft Eingaben: Er liest ein Wort Zeichen für Zeichen, wechselt dabei seinen Zustand und nimmt das Wort am Ende an oder lehnt es ab.

• Eingabealphabet:\(\Sigma\) — die endliche Menge der erlaubten Zeichen, z. B. \(\Sigma=\{a,\,b\}\).
• Wort:eine Folge von Zeichen aus \(\Sigma\), z. B. abba; \(\varepsilon\) ist das leere Wort.
• Zustände:endlich viele, als Kreise gezeichnet.
• Startzustand:genau einer, markiert durch einen Pfeil ohne Ausgangszustand.
• Endzustände:beliebig viele (auch keiner), als Doppelkreis gezeichnet.
• Übergänge:für jeden Zustand und jedes Zeichen genau ein Folgezustand — daher „deterministisch“.

Der Automat unten akzeptiert genau die Wörter über \(\{a,\,b\}\), die mit a beginnen und mit b enden. Tippe zuerst, ob er das Wort auf dem Band annimmt — dann lass ihn das Wort Zeichen für Zeichen verarbeiten.

Halte fest: Entscheidend ist allein der Zustand nach dem letzten Zeichen. Wer unterwegs einen Endzustand durchläuft, ist noch nicht angenommen — und aus dem Fehlerzustand gibt es kein Zurück.

Ob ein Wort angenommen wird, zeigt die Zustandsfolge. Dieselben Übergänge lassen sich statt im Graphen auch in einer Tabelle angeben.

• Verarbeitung:im Startzustand beginnen, je Zeichen genau einem Übergang folgen.
• Akzeptieren:nach dem letzten Zeichen in einem Endzustand — sonst abgelehnt.
• Zustandsfolge:aab: z0 \(\xrightarrow{a}\) z1 \(\xrightarrow{a}\) z1 \(\xrightarrow{b}\) z2 — akzeptiert.
• Sprache:\(L(A)\) ist die Menge aller Wörter, die der Automat \(A\) akzeptiert.
• Übergangstabelle:eine Zeile je Zustand, eine Spalte je Zeichen, im Feld der Folgezustand.
• Fehlerzustand:zF nimmt nie wieder an; er darf im Graphen fehlen, wenn das ausdrücklich vermerkt ist.

Übergangstabelle zum Automaten aus dem Applet (→ Startzustand, doppelt unterstrichen: Endzustand):