Lektion 1.1

Deterministische endliche Automaten (DEA)

30 min Lesezeit

Ein Getränkeautomat muss sich merken, wie viel Geld schon eingeworfen wurde. Eine Ampelsteuerung merkt sich, in welcher Phase sie sich gerade befindet. Ein Texteditor, der Zahlen im Quelltext erkennen soll, muss wissen, ob er sich gerade mitten in einer Zahl befindet. In all diesen Fällen braucht das System einen Speicher, der aber nur eine feste, kleine Menge an Information trägt: den aktuellen Zustand.

Der endliche Automat ist das einfachste Rechnermodell mit genau dieser Eigenschaft. Er liest ein Wort Zeichen für Zeichen, wechselt dabei nach festen Regeln den Zustand und entscheidet am Ende, ob er das Wort akzeptiert. Trotz seiner Einfachheit steckt er in jedem Compiler (lexikalische Analyse) und in den regulären Ausdrücken. Du kannst Automaten im Werkzeug Automaten-Simulator zeichnen und Wörter schrittweise durchlaufen lassen.

Definition

Alphabet, Wort und Sprache

Ein Alphabet $\Sigma$ ist eine endliche, nichtleere Menge von Zeichen, zum Beispiel $\Sigma = \{0, 1\}$ . Ein Wort über $\Sigma$ ist eine endliche Folge von Zeichen aus $\Sigma$ . Das leere Wort $\varepsilon$ enthält kein Zeichen. Die Menge aller Wörter über $\Sigma$ schreibt man $\Sigma^*$ .

Eine Sprache ist eine Teilmenge $L \subseteq \Sigma^*$ , also einfach eine Menge von Wörtern. Beispiel: Die Sprache aller Wörter über $\{0,1\}$ mit einer geraden Anzahl von Einsen. Die zentrale Frage lautet: Für welche Sprachen gibt es einen Automaten, der genau ihre Wörter akzeptiert?

L \subseteq \Sigma^*, \qquad \Sigma^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots\}

Definition

Deterministischer endlicher Automat (DEA)

Ein DEA ist ein Tupel $A = (Q, \Sigma, \delta, q_0, F)$ aus fünf Bestandteilen:

$Q$ : endliche Menge von Zuständen
$\Sigma$ : Eingabealphabet
$\delta: Q \times \Sigma \to Q$ : Übergangsfunktion. Sie sagt für jeden Zustand und jedes Zeichen genau, in welchen Zustand gewechselt wird. Das ist das „deterministisch": Es gibt nie eine Wahl.
$q_0 \in Q$ : Startzustand
$F \subseteq Q$ : Menge der Endzustände (akzeptierende Zustände)

Der Automat startet in $q_0$ , liest das Wort von links nach rechts und wendet bei jedem Zeichen $\delta$ an. Er akzeptiert das Wort, wenn er nach dem letzten Zeichen in einem Zustand aus $F$ steht. Die Menge aller akzeptierten Wörter ist die vom Automaten erkannte Sprache $L(A)$ .

A = (Q, \Sigma, \delta, q_0, F), \qquad L(A) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}

Beispiel

Gerade Anzahl von Einsen

Sprache: alle Wörter über $\{0, 1\}$ mit einer geraden Anzahl von Einsen (null zählt als gerade). Der Automat muss sich nur merken, ob bisher eine gerade oder ungerade Zahl von Einsen gelesen wurde. Zwei Zustände genügen: $g$ (gerade, Start und Endzustand) und $u$ (ungerade).

Eine $0$ ändert nichts: $\delta(g, 0) = g$ und $\delta(u, 0) = u$ . Eine $1$ kippt die Parität: $\delta(g, 1) = u$ und $\delta(u, 1) = g$ .

\delta(g,0)=g,\quad \delta(g,1)=u,\quad \delta(u,0)=u,\quad \delta(u,1)=g

Das Wort $1101$ führt zu $g \to u \to g \to g \to u$ , endet in $u$ und wird nicht akzeptiert (drei Einsen). Das Wort $1001$ führt zu $g \to u \to u \to u \to g$ und wird akzeptiert. Das leere Wort $\varepsilon$ endet im Startzustand $g$ und wird ebenfalls akzeptiert.

Beispiel

Wörter, die auf $01$ enden

Der Automat soll alle Wörter über $\{0, 1\}$ akzeptieren, die mit $01$ enden. Er merkt sich, wie viel vom Suffix $01$ gerade erreicht ist: $q_0$ (nichts), $q_1$ (letztes Zeichen war $0$ ), $q_2$ (die letzten zwei Zeichen sind $01$ , Endzustand).

\begin{array}{c|cc} \delta & 0 & 1 \\ \hline q_0 & q_1 & q_0 \\ q_1 & q_1 & q_2 \\ q_2 & q_1 & q_0 \end{array}

Das Wort $1101$ läuft $q_0 \to q_0 \to q_0 \to q_1 \to q_2$ und wird akzeptiert. Das Wort $0110$ läuft $q_0 \to q_1 \to q_2 \to q_0 \to q_1$ und wird nicht akzeptiert, weil es auf $10$ endet. Beachte, dass jeder Zustand für jedes Zeichen genau einen Übergang hat: Die Tabelle ist vollständig.

Zusammenfassung

Ein DEA ist ein Tupel $(Q, \Sigma, \delta, q_0, F)$ mit endlich vielen Zuständen und einer Übergangsfunktion, die jedem Paar aus Zustand und Zeichen genau einen Folgezustand zuordnet.
Er akzeptiert ein Wort, wenn er danach in einem Endzustand steht.
Die Menge der akzeptierten Wörter ist die erkannte Sprache $L(A)$ .
Zustände sind das Gedächtnis des Automaten: Beim Entwurf überlegst du, was er sich merken muss.
Endliche Automaten können nicht beliebig zählen, etwa $\{0^n 1^n\}$ nicht erkennen.

Übungen

Aufgabe 1Multiple Choice

Welches Wort wird vom DEA für „endet auf $01$ " akzeptiert?

Aufgabe 2Numerisch

Wie viele Zustände braucht ein DEA für die Sprache „gerade Anzahl von Einsen" mindestens?

Aufgabe 3Numerisch

Der DEA für „gerade Anzahl von Einsen" liest das Wort $0110101$ . Wie oft wechselt er dabei zwischen den Zuständen $g$ und $u$ ?

Aufgabe 4Freitext

Entwirf einen DEA über $\{0, 1\}$ , der genau die Wörter akzeptiert, deren Länge durch $3$ teilbar ist. Gib Zustände, Startzustand, Endzustände und die Übergänge an.

Gerade Anzahl von Einsen

Wörter, die auf 010101 enden

Zusammenfassung

Übungen

Wörter, die auf $01$ enden