Zustandsübergangsdiagramme
Am Bahnhof in Köln wirfst du eine Münze in den Fahrkartenautomaten, drückst eine Taste und erhältst dein Ticket. Der Automat „weiß“ in jedem Moment, was er als Nächstes tun darf: erst bezahlen, dann wählen. Aber woher weiß er das? Und wie kannst du so ein Verhalten genau beschreiben, ohne eine Zeile Programmcode zu schreiben? Genau dafür gibt es endliche Automaten.
Zustände, Eingaben und Übergänge
Ein Getränkeautomat hat zwei „Situationen“: Entweder wartet er auf Geld oder er hat Geld erhalten. Diese Situationen nennt man Zustände. Was von außen passiert (Münze einwerfen, Taste drücken), sind die Eingaben. Eine Eingabe kann den Automaten in einen anderen Zustand bringen: Das ist ein Übergang.
Das Zustandsübergangsdiagramm zeichnet das als Graph: Zustände sind Kreise, Übergänge sind Pfeile mit der Eingabe als Beschriftung. Der Startzustand hat einen Pfeil von außen, ein Endzustand einen Doppelkreis.
Dieselbe Information passt in eine Übergangstabelle: Zeilen sind die Zustände, Spalten die Eingaben, in den Feldern steht der Folgezustand.
| Zustand | 1-€-Münze | Taste „Wasser“ |
|---|---|---|
bereit (Start) |
bezahlt |
bereit |
bezahlt |
bezahlt |
bereit |
Ein Getränkeautomat hat die Zustände bereit und bezahlt. Der Einwurf einer 1-€-Münze führt von bereit nach bezahlt, das Drücken der Taste „Wasser“ führt von bezahlt…
Ein Getränkeautomat hat die Zustände bereit und bezahlt. Der Einwurf einer 1-€-Münze führt von bereit nach bezahlt, das Drücken der Taste „Wasser“ führt von bezahlt zurück nach bereit. Nach dem Einschalten befindet sich der Automat im Zustand bereit.
- a) Nenne Zustände, Eingaben und den Startzustand.
- b) Beschreibe, was passiert, wenn in
bereitdie Taste „Wasser“ gedrückt wird.
Eine Ampel für Fußgänger hat die Zustände rot und grün. Beim Drücken der Taste wechselt sie von rot nach grün, nach Ablauf der Zeit von grün nach rot. Beschreibe das…
Eine Ampel für Fußgänger hat die Zustände rot und grün. Beim Drücken der Taste wechselt sie von rot nach grün, nach Ablauf der Zeit von grün nach rot.
Beschreibe das Zustandsübergangsdiagramm in einer Tabelle: Liste alle Übergänge mit Ausgangszustand, Eingabe und Folgezustand auf.
Eingaben durchspielen und akzeptieren
Um zu prüfen, was ein Automat mit einer Eingabe macht, beginnst du im Startzustand und liest Zeichen für Zeichen. Bei jedem Zeichen folgst du dem passenden Pfeil. Am Ende schaust du, wo du stehst: In einem Endzustand? Dann wird die Eingabe akzeptiert, sonst nicht.
Beispiel: Dieser Automat hat die Zustände $A$ (Start) und $B$ (Endzustand). Er akzeptiert Wörter aus 0 und 1, die mit 1 enden.
| Zustand | 0 | 1 |
|---|---|---|
| $A$ (Start) | $A$ | $B$ |
| $B$ (Ende) | $A$ | $B$ |
Ein Automat hat die Zustände $A$ (Start), $B$ und $C$ (Endzustand). Übergänge: $A \xrightarrow{0} A$, $A \xrightarrow{1} B$, $B \xrightarrow{0} C$,…
Ein Automat hat die Zustände $A$ (Start), $B$ und $C$ (Endzustand). Übergänge: $A \xrightarrow{0} A$, $A \xrightarrow{1} B$, $B \xrightarrow{0} C$, $B \xrightarrow{1} B$, $C \xrightarrow{0} C$, $C \xrightarrow{1} B$.
Prüfe für die Eingaben 0110, 10 und 111, in welchem Zustand der Automat endet und ob die Eingabe akzeptiert wird.
Ein Drehkreuz im Phantasialand hat die Zustände gesperrt und offen. Eingaben: Karte (gültiges Ticket) und Drehen. Karte öffnet das Drehkreuz, Drehen sperrt es wieder.…
Ein Drehkreuz im Phantasialand hat die Zustände gesperrt und offen. Eingaben: Karte (gültiges Ticket) und Drehen. Karte öffnet das Drehkreuz, Drehen sperrt es wieder. Karte im Zustand offen ändert nichts, Drehen im Zustand gesperrt ändert nichts.
- a) Stelle die Übergangstabelle auf.
- b) Das Drehkreuz ist anfangs
gesperrt. Verfolge die EingabefolgeDrehen, Karte, Karte, Drehen, Drehenund gib die Zustandsfolge an.
Automaten entwickeln
Jetzt drehen wir es um: Du bekommst eine Aufgabe und baust den Automaten. Der Trick: Zustände sind das Gedächtnis des Automaten. Frage dich bei jedem Zustand: „Was muss ich mir bis hierhin gemerkt haben?“
Zwei typische Muster:
Entwickle einen Automaten, der Wörter aus den Zeichen a und b akzeptiert, die mit ab enden. Gib Zustände, Startzustand, Endzustand und die Übergangstabelle an und teste…
Entwickle einen Automaten, der Wörter aus den Zeichen a und b akzeptiert, die mit ab enden. Gib Zustände, Startzustand, Endzustand und die Übergangstabelle an und teste aab, ba und abab.
Ein Automat soll Binärzahlen akzeptieren, die eine gerade Anzahl an Einsen enthalten. a) Wie viele Zustände braucht er mindestens? Begründe. b) Gib die Übergangstabelle…
Ein Automat soll Binärzahlen akzeptieren, die eine gerade Anzahl an Einsen enthalten.
- a) Wie viele Zustände braucht er mindestens? Begründe.
- b) Gib die Übergangstabelle an.
- c) Teste
1011,0000und111.
Ein Schließfach in einem Bahnhof öffnet sich nur nach der Codefolge 1, 2, 3 (direkt hintereinander). Bei jeder falschen Eingabe beginnt die Eingabe von vorn (bei 1 nach…
Ein Schließfach in einem Bahnhof öffnet sich nur nach der Codefolge 1, 2, 3 (direkt hintereinander). Bei jeder falschen Eingabe beginnt die Eingabe von vorn (bei 1 nach einer falschen Eingabe zählt diese 1 bereits als Anfang). Ist das Fach einmal offen, bleibt es offen – weitere Eingaben ändern den Zustand nicht mehr.
- a) Entwickle den Automaten mit vollständiger Übergangstabelle (Eingaben
1,2,3).
- b) Teste
1123,1213und123.
- c) Begründe, warum der Automat sich keine beliebig lange Eingabe merken muss.
Automaten analysieren und Grenzen
Oft ist ein Automat gegeben und du sollst herausfinden, was er erkennt. Gehe so vor: Teste einige kurze Wörter, suche die kürzesten akzeptierten Wörter und überlege, was jeder Zustand bedeutet. Ein akzeptierender Zustand, aus dem man nicht mehr herauskommt, bedeutet: Ab hier wird jede Fortsetzung akzeptiert.
Ein Beispiel mit Beträgen: Ein Parkautomat nimmt 50-Cent- und 1-€-Münzen und gibt ab 1,50 € einen Schein aus. Zustände sind der Betrag bisher: 0, 50, 100 (Cent). Sobald 150 Cent erreicht sind, gibt er den Schein aus (eine Ausgabe) und geht zurück in den Zustand 0. Das ist ein Automat mit Ausgabe: In der Tabelle stehen Folgezustand und Ausgabe getrennt, in der Form „Folgezustand / Ausgabe“.
| Zustand | 50 Cent | 1 € |
|---|---|---|
| 0 (Start) | 50 / – | 100 / – |
| 50 | 100 / – | 0 / Schein |
| 100 | 0 / Schein | 0 / Schein |
Der Parkautomat kommt mit wenigen Zuständen aus, weil er nur bis zur Obergrenze von 1,50 € zählen muss. Würde er jeden beliebig hohen Betrag genau merken müssen, bräuchte er unendlich viele Zustände. Das kann ein endlicher Automat nicht.
Auch bei einer Codefolge mit festem Muster reichen wenige Zustände: Er merkt sich nur, wie weit das Muster schon erkannt wurde, nicht die gesamte Eingabe.
Gegeben ist folgender Automat: Zustände $S$ (Start), $T$, $U$ (Endzustand). Übergänge: $S \xrightarrow{a} T$, $S \xrightarrow{b} S$, $T \xrightarrow{a} U$,…
Gegeben ist folgender Automat: Zustände $S$ (Start), $T$, $U$ (Endzustand). Übergänge: $S \xrightarrow{a} T$, $S \xrightarrow{b} S$, $T \xrightarrow{a} U$, $T \xrightarrow{b} S$, $U \xrightarrow{a} U$, $U \xrightarrow{b} U$.
- a) Beschreibe in Worten, welche Wörter akzeptiert werden.
- b) Gib das kürzeste akzeptierte Wort, ein akzeptiertes Wort der Länge 3 und ein nicht akzeptiertes Wort der Länge 4 an.
- c) Ändere den Automaten so, dass er genau die Wörter akzeptiert, die
aaaenthalten.
Ein Parkautomat in Münster akzeptiert 50-Cent- und 1-€-Münzen und gibt einen Parkschein aus, sobald mindestens 1,50 € eingeworfen wurden. Danach beginnt er von vorn…
Ein Parkautomat in Münster akzeptiert 50-Cent- und 1-€-Münzen und gibt einen Parkschein aus, sobald mindestens 1,50 € eingeworfen wurden. Danach beginnt er von vorn (kein Wechselgeld).
- a) Bestimme die nötigen Zustände (Betrag bisher) und gib die Zustandsübergangstabelle an.
- b) Prüfe die Folgen
50, 50, 50,100, 50und100, 100.
- c) Erkläre, warum ein Automat mit endlich vielen Zuständen für diese Aufgabe ausreicht, aber nicht für beliebig hohe Beträge ohne Obergrenze.
Zurück zum Anfang: Der Fahrkartenautomat weiß, was er tun darf, weil er sich in einem Zustand befindet. Jede Eingabe ändert diesen Zustand nach festen Regeln der Übergangstabelle.
Auf einen Blick
-
Ein endlicher Automat hat Zustände, einen Startzustand, Eingaben, Übergänge und oft Endzustände.
-
Das Zustandsübergangsdiagramm zeigt Zustände als Kreise und Übergänge als beschriftete Pfeile. Die Übergangstabelle enthält dieselbe Information.
-
Eine Eingabe wird Zeichen für Zeichen vom Startzustand aus gelesen. Sie ist akzeptiert, wenn sie in einem Endzustand endet.
-
Zu jedem Zustand und jeder Eingabe gehört genau ein Übergang, auch Schleifen.
-
Beim Entwickeln gilt: Zustände sind das Gedächtnis. Überlege, was du dir merken musst, und teste mit Randfällen.
-
Endliche Automaten können nur endlich viel merken, unbegrenztes Zählen schaffen sie nicht.