Endliche Automaten: Verhalten, Tabelle und Graph
Ein Fahrkartenautomat der S-Bahn Rhein-Ruhr hat keinen Zettel, auf dem er sich die eingeworfenen Münzen notiert. Er „weiß“ nur, in welcher Situation er gerade ist: noch nichts bezahlt, erst die Hälfte bezahlt, Ticket kann ausgegeben werden. Jede neue Münze verändert diese Situation. Genau so arbeitet ein endlicher Automat. Am Ende der Seite können Sie erklären, wie so ein Automat mit einer festen, kleinen Anzahl von Situationen beliebig lange Eingaben prüft.
Bausteine eines endlichen Automaten
Ein endlicher Automat liest ein Wort (eine Folge von Zeichen) von links nach rechts, immer genau ein Zeichen pro Schritt. Er hat dabei nur ein sehr kleines „Gedächtnis“: seinen aktuellen Zustand. Nach jedem Zeichen wechselt er (oder bleibt) im Zustand. Am Ende entscheidet der Zustand, ob das Wort akzeptiert wird.
Ein Wort wird akzeptiert, wenn der Automat nach dem Lesen des letzten Zeichens in einem Endzustand steht. Die Menge aller akzeptierten Wörter heißt die akzeptierte Sprache $L$ des Automaten. Das leere Wort $\varepsilon$ hat keine Zeichen. Der Automat bleibt dabei im Startzustand. Es wird also genau dann akzeptiert, wenn der Startzustand auch Endzustand ist.
Als Beispiel dient ein Automat über $\Sigma=\{0,1\}$, der genau die Wörter akzeptiert, die mit einer 1 beginnen. Er hat drei Zustände:
-
$s_0$: noch nichts gelesen (Start),
-
$s_1$: das erste Zeichen war eine 1 (Endzustand),
-
$f$: das erste Zeichen war eine 0, das Wort ist „verloren“ (Fangzustand).
Lesehilfe: Der Pfeil von außen markiert den Startzustand. Ein Doppelkreis markiert einen Endzustand. Ein Pfeil mit Beschriftung $x$ von $p$ nach $q$ bedeutet $\delta(p,x)=q$. Eine Beschriftung „0, 1“ steht für zwei Übergänge mit demselben Ziel.
Ein endlicher Automat hat die Zustände $q_0$, $q_1$, $q_2$, das Eingabealphabet $\{a, b\}$, den Startzustand $q_0$ und den einzigen Endzustand $q_2$. Die Übergänge…
Ein endlicher Automat hat die Zustände $q_0$, $q_1$, $q_2$, das Eingabealphabet $\{a, b\}$, den Startzustand $q_0$ und den einzigen Endzustand $q_2$. Die Übergänge lauten:
$\delta(q_0,a)=q_1$, $\delta(q_0,b)=q_0$, $\delta(q_1,a)=q_1$, $\delta(q_1,b)=q_2$, $\delta(q_2,a)=q_2$, $\delta(q_2,b)=q_2$.
- a) Stellen Sie die Übergangstabelle des Automaten auf.
- b) Zeichnen Sie den zugehörigen Zustandsgraphen oder beschreiben Sie ihn vollständig (Knoten, Pfeile mit Beschriftung, Start- und Endzustand).
Übergangstabelle und Zustandsgraph
Ein Automat lässt sich auf zwei gleichwertige Arten darstellen. Beide enthalten genau dieselbe Information.
-
Der Zustandsgraph ist anschaulich: Knoten sind Zustände, beschriftete Pfeile sind Übergänge.
-
Die Übergangstabelle ist vollständig und lässt sich leicht prüfen: Die Zeilen sind die Zustände, die Spalten die Zeichen, im Feld steht der Folgezustand.
Der Beispielautomat von oben als Tabelle:
| 0 | 1 | |
|---|---|---|
| $\rightarrow s_0$ | $f$ | $s_1$ |
| $(s_1)$ | $s_1$ | $s_1$ |
| $f$ | $f$ | $f$ |
Üblich ist: Pfeil $\rightarrow$ vor dem Startzustand, Klammern (oder ein Stern) um die Endzustände. Bei einem DEA ist jedes Feld der Tabelle gefüllt. Im Graphen geht daher aus jedem Knoten für jedes Zeichen genau ein Pfeil heraus.
Wörter verarbeiten und die akzeptierte Sprache
Um ein Wort zu prüfen, geht man den Graphen Zeichen für Zeichen ab (oder liest die Tabelle). Das Protokoll ist die Zustandsfolge. Sie hat immer ein Element mehr als das Wort Zeichen hat.
Die akzeptierte Sprache beschreibt man in Worten oder mit einer Eigenschaft, etwa „alle Wörter über $\{a,b\}$ mit einer ungeraden Anzahl von $a$“. Zum Ermitteln der Sprache stellt man sich bei jedem Zustand die Frage: „Was habe ich gelesen, wenn ich hier stehe?“
Gegeben ist ein Automat mit den Zuständen $s_0$ (Start), $s_1$ (Endzustand) und dem Alphabet $\{0,1\}$. Es gilt: $\delta(s_0,0)=s_0$, $\delta(s_0,1)=s_1$,…
Gegeben ist ein Automat mit den Zuständen $s_0$ (Start), $s_1$ (Endzustand) und dem Alphabet $\{0,1\}$. Es gilt: $\delta(s_0,0)=s_0$, $\delta(s_0,1)=s_1$, $\delta(s_1,0)=s_1$, $\delta(s_1,1)=s_0$.
Entscheiden Sie jeweils, ob der Automat das Wort akzeptiert, und geben Sie die durchlaufene Zustandsfolge an:
- a) $0110$
- b) $1000$
- c) $11$
- d) $\varepsilon$ (das leere Wort)
Ein Automat für das Alphabet $\{a,b\}$ hat den Startzustand $A$, den Endzustand $B$ und die Übergänge $A\xrightarrow{a}B$, $A\xrightarrow{b}A$, $B\xrightarrow{a}B$,…
Ein Automat für das Alphabet $\{a,b\}$ hat den Startzustand $A$, den Endzustand $B$ und die Übergänge $A\xrightarrow{a}B$, $A\xrightarrow{b}A$, $B\xrightarrow{a}B$, $B\xrightarrow{b}B$.
- a) Geben Sie drei Wörter der Länge 3 an, die akzeptiert werden, und ein Wort, das nicht akzeptiert wird.
- b) Beschreiben Sie die akzeptierte Sprache in Worten.
Automaten entwickeln
Beim Entwurf geht man umgekehrt vor: Die Sprache ist gegeben, der Automat gesucht. Die Kernfrage lautet: Was muss sich der Automat merken? Jede unterscheidbare Antwort wird ein Zustand.
Eine Modifikation eines vorhandenen Automaten ist oft einfacher als ein Neubau. Man ändert zum Beispiel die Menge der Endzustände. Vertauscht man Endzustände und Nicht-Endzustände, akzeptiert der Automat genau die Wörter, die vorher abgelehnt wurden (bei einem vollständigen DEA).
Der Eingang eines Fahrradparkhauses in Münster wird von einem Automaten gesteuert. Es werden nur Münzen zu 1 € (Zeichen $e$) und 2 € (Zeichen $z$) eingeworfen. Das…
Der Eingang eines Fahrradparkhauses in Münster wird von einem Automaten gesteuert. Es werden nur Münzen zu 1 € (Zeichen $e$) und 2 € (Zeichen $z$) eingeworfen. Das Parkhaus öffnet, sobald mindestens 3 € eingeworfen wurden (Endzustand). Weitere Münzen ändern daran nichts.
- a) Entwickeln Sie einen endlichen Automaten (Zustände nach eingeworfenem Betrag: 0 €, 1 €, 2 €, „≥ 3 €“) und geben Sie ihn als Graphen und als Tabelle an.
- b) Prüfen Sie die Wörter $ez$, $ee$, $zz$ und $eee$ mit Ihrem Automaten.
Entwerfen Sie einen deterministischen endlichen Automaten über dem Alphabet $\{0,1\}$, der genau die Wörter akzeptiert, die eine gerade Anzahl von Einsen enthalten. a)…
Entwerfen Sie einen deterministischen endlichen Automaten über dem Alphabet $\{0,1\}$, der genau die Wörter akzeptiert, die eine gerade Anzahl von Einsen enthalten.
- a) Geben Sie den Graphen und die Übergangstabelle an.
- b) Ändern Sie den Automaten so, dass er genau die Wörter mit einer ungeraden Anzahl von Einsen akzeptiert. Welche Änderung genügt?
- c) Begründen Sie, warum der Automat mit zwei Zuständen auskommt.
Sprache aus Tabelle oder Graph ermitteln
Hier gehen Sie vom fertigen Automaten zur Beschreibung der Sprache. Eine bewährte Methode:
Gegeben ist die Übergangstabelle (Start: $z_0$, Endzustand: $z_3$): | | a | b | |---|---|---| | $z_0$ | $z_1$ | $z_0$ | | $z_1$ | $z_1$ | $z_2$ | | $z_2$ | $z_1$ | $z_3$…
Gegeben ist die Übergangstabelle (Start: $z_0$, Endzustand: $z_3$):
| a | b | |
|---|---|---|
| $z_0$ | $z_1$ | $z_0$ |
| $z_1$ | $z_1$ | $z_2$ |
| $z_2$ | $z_1$ | $z_3$ |
| $z_3$ | $z_3$ | $z_3$ |
- a) Zeichnen Sie den Zustandsgraphen.
- b) Ermitteln Sie die akzeptierte Sprache und beschreiben Sie sie in Worten.
- c) Geben Sie das kürzeste akzeptierte Wort an.
Anspruchsvollere Entwürfe: Endungen, verbotene Teilwörter, Reste
Bei schwierigeren Sprachen hilft ein Gedanke: Der Zustand speichert genau den Teil der Vergangenheit, der für die Zukunft noch zählt.
Wörter mit bestimmter Endung
Soll das Wort auf ein Muster enden, muss sich der Automat merken, wie viel vom Muster am Ende des bisher gelesenen Wortes schon steht. Jeder Fortschritt im Muster ist ein Zustand. Bei einem falschen Zeichen fällt man nicht immer auf den Start zurück. Oft passt der letzte gelesene Buchstabe schon wieder zum Anfang des Musters.
Verbotene Teilwörter und Fangzustand
Sollen bestimmte Teilwörter nicht vorkommen, führt das Auftreten in eine Sackgasse, den Fangzustand. Er ist kein Endzustand und hat nur Pfeile zu sich selbst. Er macht den Automaten vollständig: Ohne ihn wüsste der Automat bei dem verbotenen Zeichen nicht weiter, es fehlte ein Übergang.
Rechnen mit Resten
Zahlen werden oft Ziffer für Ziffer gelesen. Dabei muss man sich nur den Rest merken, nicht die ganze Zahl. Im Dezimalsystem gilt: Hängt man die Ziffer $x$ an eine Zahl mit Wert $w$ an, entsteht $10\,w + x$. Ist man nur am Rest modulo $m$ interessiert, genügt $r$ als Zustand, und der neue Rest ist $(10\,r + x) \bmod m$. Im Dualsystem ersetzt der Faktor 2 die 10: Anhängen eines Bits verdoppelt den bisherigen Wert und addiert das Bit.
Grenzen endlicher Automaten
Ein endlicher Automat hat nur endlich viele Zustände, also nur ein begrenztes Gedächtnis. Er kann daher nicht unbegrenzt zählen: Eine Sprache wie „genauso viele $a$ wie $b$“ erkennt kein endlicher Automat, denn dafür bräuchte er für jede Anzahl einen eigenen Zustand. Genau die Sprachen, die ein endlicher Automat erkennt, lassen sich auch mit regulären Grammatiken erzeugen: Jeder Zustand entspricht einem Nichtterminal, jeder Übergang einer Regel. Dieselbe Grenze gilt für beide: Sprachen, die unbegrenztes Zählen erfordern, sind weder durch einen endlichen Automaten noch durch eine reguläre Grammatik beschreibbar. Mehr dazu auf der Seite „Reguläre Grammatiken und Grenzen“.
Ein Automat soll über $\{0,1\}$ genau die Wörter akzeptieren, die auf $01$ enden. a) Entwickeln Sie einen deterministischen Automaten mit möglichst wenigen Zuständen.…
Ein Automat soll über $\{0,1\}$ genau die Wörter akzeptieren, die auf $01$ enden.
- a) Entwickeln Sie einen deterministischen Automaten mit möglichst wenigen Zuständen. Geben Sie Graph und Tabelle an und erläutern Sie die Bedeutung jedes Zustands.
- b) Zeigen Sie an den Wörtern $1001$, $0110$ und $01$, dass Ihr Automat korrekt arbeitet.
- c) Modifizieren Sie den Automaten so, dass er Wörter akzeptiert, die auf $01$ enden oder das leere Wort sind. Begründen Sie Ihre Änderung.
Ein Automat über $\{a,b\}$ soll die Wörter akzeptieren, die weder das Teilwort $aa$ noch das Teilwort $bb$ enthalten. a) Entwickeln Sie einen vollständigen…
Ein Automat über $\{a,b\}$ soll die Wörter akzeptieren, die weder das Teilwort $aa$ noch das Teilwort $bb$ enthalten.
- a) Entwickeln Sie einen vollständigen deterministischen Automaten (einschließlich eines Fangzustands).
- b) Beschreiben Sie die Sprache durch eine Aussage über die Buchstabenfolge.
- c) Begründen Sie, warum ein Fangzustand nötig ist, wenn der Automat vollständig sein soll.
Ein Automat verarbeitet Binärzahlen, die Bit für Bit mit dem höchstwertigen Bit zuerst eingelesen werden. Er soll genau die Wörter akzeptieren, deren Zahlenwert durch 3…
Ein Automat verarbeitet Binärzahlen, die Bit für Bit mit dem höchstwertigen Bit zuerst eingelesen werden. Er soll genau die Wörter akzeptieren, deren Zahlenwert durch 3 teilbar ist. Die Zustände entsprechen dem Rest bei Division durch 3 (0, 1, 2).
- a) Begründen Sie, dass beim Einlesen eines Bits $x$ aus dem Rest $r$ der neue Rest $(2r+x) \bmod 3$ entsteht.
- b) Stellen Sie die Übergangstabelle auf und zeichnen Sie den Graphen.
- c) Testen Sie die Wörter $110$, $1001$ und $111$.
Auf einen Blick
Zurück zum Anfang: Der Fahrkartenautomat braucht kein Notizbuch. Seine endlich vielen Zustände („0 €“, „1 €“, „genug bezahlt“) fassen alles zusammen, was für die Entscheidung zählt.