Aufgaben: Zustandsübergangsdiagramme

Ein Automat für eine Schranke hat die Zustände „geschlossen“ und „offen“. Mit der Eingabe „Ticket“ wechselt er von „geschlossen“ zu „offen“, mit der Eingabe „Auto durch“ von „offen“ zu „geschlossen“. Zu Beginn ist die Schranke geschlossen.

1. a) Nenne den Startzustand und die beiden Eingaben.

1. b) Welchen Zustand hat der Automat nach der Eingabefolge: Ticket, Auto durch, Ticket?

Erkläre die Begriffe Zustand, Übergang, Eingabe und Startzustand bei einem Zustandsübergangsdiagramm. Wie werden Zustände und Übergänge im Diagramm dargestellt?

Eine Ampel für Fußgänger hat die Zustände ROT und GRÜN. Der Knopf „Drücken“ schaltet von ROT auf GRÜN, die Eingabe „Zeit um“ schaltet von GRÜN auf ROT. Bei „Zeit um“ in ROT und „Drücken“ in GRÜN passiert nichts.

Schreibe die Übergänge (Zustand, Eingabe, Folgezustand) in Worten oder als Tabelle vollständig auf.

Ein Getränkeautomat in der Schule nimmt nur 1-€-Münzen an. Eine Flasche Wasser kostet 2 €. Zustände: 0 € (Start), 1 €, 2 € (Flasche wird ausgegeben, dann zurück zu 0 €). Eingaben: „Münze“.

1. a) Erstelle die Übergangstabelle.

1. b) In welchem Zustand befindet sich der Automat nach 5 Münzen? Wie viele Flaschen wurden ausgegeben?

Ein Automat liest ein Wort aus den Zeichen a und b und soll erkennen, ob es mit ab endet. Zustände: S (Start), A (letztes Zeichen war a), B (letzte beiden Zeichen waren ab, Endzustand). Übergänge: S–a→A, S–b→S, A–a→A, A–b→B, B–a→A, B–b→S.

1. a) Prüfe die Wörter aab, abb und baab: Welche werden akzeptiert?

1. b) Gib ein weiteres Wort mit 5 Zeichen an, das akzeptiert wird.

Ein Türschloss öffnet sich nur, wenn nacheinander die Tasten 1, 7, 3 gedrückt werden. Bei jeder falschen Taste geht der Automat zurück in den Startzustand (Ausnahme: Bei einer 1 im Startzustand oder in einem anderen Zustand geht er in den Zustand „1 erkannt“).

1. a) Entwickle den Automaten: Nenne die Zustände und stelle die Übergangstabelle auf.

1. b) Prüfe die Eingabefolgen 1-7-7-3 und 1-1-7-3.

Ein Automat verarbeitet Binärzahlen (Zeichen 0 und 1) und soll erkennen, ob die Anzahl der gelesenen Einsen gerade ist.

1. a) Entwickle den Automaten mit möglichst wenig Zuständen. Lege Startzustand und Endzustand fest und gib die Übergangstabelle an.

1. b) Prüfe die Eingaben 10110 und 0000.

1. c) Begründe, warum zwei Zustände ausreichen, obwohl die Eingabe beliebig lang sein kann.

Ein Fahrkartenautomat der Stadtwerke Köln akzeptiert 1-€- und 2-€-Münzen. Ein Kurzstreckenticket kostet 3 €. Sobald mindestens 3 € eingeworfen wurden, wird das Ticket ausgegeben, danach beginnt der Automat bei 0 €. Wechselgeld wird nicht betrachtet.

1. a) Bestimme die nötigen Zustände.

1. b) Stelle die Übergangstabelle für die Eingaben „1 €“ und „2 €“ auf.

1. c) Wie viele verschiedene Münzfolgen führen vom Startzustand genau zur Ticketausgabe, ohne dass vorher ein Ticket ausgegeben wurde? Zähle sie auf.

Ein Automat soll in einer Folge aus 0 und 1 das Muster 101 erkennen (Endzustand, sobald 101 zuletzt gelesen wurde; Überlappungen sind erlaubt, z. B. in 10101).

1. a) Entwickle den Automaten mit Zuständen und Übergangstabelle.

1. b) Teste ihn mit 1101 und 10101 und gib jeweils die Zustandsfolge an.

1. c) Erkläre, was jeder Zustand „sich merkt“.