Deterministische endliche Automaten

Ein deterministischer endlicher Automat (DEA, englisch DFA) ist ein abstraktes Rechenmodell mit einer endlichen Menge von Zuständen. Er liest ein Eingabewort Zeichen für Zeichen, wechselt dabei zwischen Zuständen und akzeptiert das Wort, wenn er nach dem Lesen in einem Endzustand steht. DEAs erkennen genau die regulären Sprachen – das sind die einfachsten Sprachen der Chomsky-Hierarchie (Typ 3).

Ein DEA ist ein 5-Tupel \( M = (Q, \Sigma, \delta, q_0, F) \) mit:

• \( Q \) – endliche Menge von Zuständen
• \( \Sigma \) – endliches Eingabealphabet
• \( \delta : Q \times \Sigma \rightarrow Q \) – Überführungsfunktion (vollständig definiert)
• \( q_0 \in Q \) – Startzustand
• \( F \subseteq Q \) – Menge der Endzustände

Wichtig: deterministisch bedeutet, dass \( \delta \) für jeden Zustand und jedes Eingabezeichen genau einen Folgezustand liefert.

Wir konstruieren einen DEA über \( \Sigma = \{a, b\} \), der genau die Wörter mit einer geraden Anzahl von as akzeptiert. Wir brauchen zwei Zustände:

• \( q_0 \) – bisher gerade Anzahl as (Startzustand und Endzustand)
• \( q_1 \) – bisher ungerade Anzahl as

Überführungstabelle:

      | a   | b
------+-----+-----
 q0   | q1  | q0
 q1   | q0  | q1

Beim Lesen von b wechselt der Automat den Zustand nicht. Beim Lesen von a wechselt er zwischen \( q_0 \) und \( q_1 \).

Grafisch stellt man Zustände als Kreise und Übergänge als beschriftete Pfeile dar. Endzustände werden doppelt umrandet, der Startzustand bekommt einen eingehenden Pfeil ohne Quelle.

    --> (( q0 )) --a--> ( q1 )
            ^     <--a--    |
            |b              |b
            +---------------+

Das Wort abba führt über \( q_0 \rightarrow q_1 \rightarrow q_1 \rightarrow q_1 \rightarrow q_0 \) und endet im Endzustand – akzeptiert.

Die Sprache \( L(M) \) eines DEA \( M \) ist die Menge aller Wörter, die er akzeptiert. Im Beispiel: \( L(M) = \{ w \in \{a, b\}^* : |w|_a \text{ ist gerade} \} \). DEAs erkennen genau die regulären Sprachen, also die gleiche Klasse, die durch reguläre Ausdrücke und reguläre Grammatiken (Typ 3) definiert wird.

DEAs haben kein Gedächtnis außerhalb ihrer Zustände – sie können nicht zählen. Daher kann kein DEA die Sprache \( \{a^n b^n\} \) erkennen. Dafür benötigt man einen Kellerautomaten. DEAs lassen sich minimieren (kleinstmögliche Zustandszahl) und sind unter Vereinigung, Schnitt und Komplement abgeschlossen.

Unvollständige Überführungsfunktion (es fehlt ein Folgezustand für ein Eingabesymbol), Endzustände nicht doppelt eingerahmt, Verwechslung von Start- und Endzustand, Versuch, mit einem DEA zählende Sprachen zu erkennen.

Zusammenfassung: Ein DEA \( (Q, \Sigma, \delta, q_0, F) \) entscheidet, ob ein Wort zu einer regulären Sprache gehört. Er ist deterministisch, vollständig und gedächtnislos.

Abitur-Tipp: Prüfe deine DEA-Diagramme immer mit drei Beispielwörtern: einem akzeptierten, einem nicht akzeptierten und dem leeren Wort.