Aufgaben: Zustandsübergangsdiagramme

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.

1. a) Nenne Zustände, Eingaben und den Startzustand.

1. b) Beschreibe, was passiert, wenn in bereit die Taste „Wasser“ gedrückt wird.

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.

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.

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 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.

1. a) Stelle die Übergangstabelle auf.

1. b) Das Drehkreuz ist anfangs gesperrt. Verfolge die Eingabefolge Drehen, Karte, Karte, Drehen, Drehen und gib die Zustandsfolge an.

Ein Automat soll Binärzahlen akzeptieren, die eine gerade Anzahl an Einsen enthalten.

1. a) Wie viele Zustände braucht er mindestens? Begründe.

1. b) Gib die Übergangstabelle an.

1. c) Teste 1011, 0000 und 111.

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.

1. a) Entwickle den Automaten mit vollständiger Übergangstabelle (Eingaben 1, 2, 3).

1. b) Teste 1123, 1213 und 123.

1. c) Begründe, warum der Automat sich keine beliebig lange Eingabe merken muss.

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$.

1. a) Beschreibe in Worten, welche Wörter akzeptiert werden.

1. b) Gib das kürzeste akzeptierte Wort, ein akzeptiertes Wort der Länge 3 und ein nicht akzeptiertes Wort der Länge 4 an.

1. c) Ändere den Automaten so, dass er genau die Wörter akzeptiert, die aaa enthalten.

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).

1. a) Bestimme die nötigen Zustände (Betrag bisher) und gib die Zustandsübergangstabelle an.

1. b) Prüfe die Folgen 50, 50, 50, 100, 50 und 100, 100.

1. 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.