Zustandsübergangsdiagramme
An der Schranke eines Parkhauses in Köln passiert immer das Gleiche: Ticket ziehen, Schranke geht auf, Auto fährt durch, Schranke geht zu. Die Schranke „weiß“ dabei nur, ob sie gerade offen oder geschlossen ist. Wie beschreibt man so ein Gerät genau, ohne einen einzigen Befehl zu programmieren? Dafür gibt es Zustandsübergangsdiagramme.
Zustände, Eingaben und Übergänge
Viele Geräte merken sich nur ihre aktuelle „Lage“: Die Schranke ist offen oder geschlossen, die Fußgängerampel zeigt Rot oder Grün. Diese Lage nennt man Zustand. Eine Eingabe (Knopf, Münze, Zeichen) kann den Zustand ändern. Der Wechsel heißt Übergang.
Im Zustandsübergangsdiagramm zeichnet man:
-
jeden Zustand als Kreis (Endzustand: doppelter Kreis),
-
jeden Übergang als Pfeil, beschriftet mit der Eingabe,
-
den Startzustand mit einem Pfeil „von außen“.
Dasselbe kann man als Übergangstabelle schreiben. Sie ist vollständig, wenn für jeden Zustand und jede Eingabe eine Zeile vorhanden ist. Das Diagramm oben ist absichtlich verkürzt: Der Übersicht halber sind die beiden Übergänge in den gleichen Zustand (Schleifen) nicht gezeichnet. Vollständig ist erst die Tabelle, in der auch diese Schleifen stehen.
| Zustand | Eingabe | Folgezustand |
|---|---|---|
| geschlossen | Ticket | offen |
| offen | Auto durch | geschlossen |
| geschlossen | Auto durch | geschlossen |
| offen | Ticket | offen |
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“…
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.
- a) Nenne den Startzustand und die beiden Eingaben.
- 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?
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…
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.
Eingabefolgen verfolgen
Um zu prüfen, was ein Automat tut, liest du eine Eingabefolge Zeichen für Zeichen: Du startest im Startzustand, suchst in der Tabelle den Übergang und notierst den neuen Zustand. Das ist wie ein Schreibtischtest bei einem Programm.
Automaten, die Wörter prüfen
Manche Automaten entscheiden, ob ein Wort akzeptiert wird: Das Wort wird ganz gelesen. Ist der Automat danach im Endzustand, wird es akzeptiert, sonst nicht.
Beispiel: Ein Automat erkennt Wörter aus a und b, die mit ab enden. S ist der Start, B der Endzustand.
| Zustand | a | b |
|---|---|---|
| S (Start) | A | S |
| A | A | B |
| B (Ende) | A | S |
Prüfe aab: S –a→ A –a→ A –b→ B. Ende im Endzustand B, also akzeptiert. Prüfe abb: S → A → B → S. Ende in S, also nicht akzeptiert.
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 €).…
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“.
- a) Erstelle die Übergangstabelle.
- 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…
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.
- a) Prüfe die Wörter
aab,abbundbaab: Welche werden akzeptiert?
- b) Gib ein weiteres Wort mit 5 Zeichen an, das akzeptiert wird.
Einen Automaten entwickeln
Beim Entwickeln gehst du rückwärts: Du überlegst, was sich der Automat merken muss. Jede unterschiedliche „Erinnerung“ ist ein Zustand.
So sieht der Automat als Zustandsübergangsdiagramm aus (Übergänge zurück zu S bei falschen Tasten sind der Übersicht halber nicht gezeichnet, sie stehen in der Tabelle):
Automaten mit Zählen und Rest
Auch „gerade oder ungerade“ lässt sich mit wenigen Zuständen merken. Wenn gezählt werden soll, ob die Anzahl der Einsen gerade ist, muss sich der Automat nicht die ganze Zahl merken, sondern nur die Parität: gerade oder ungerade. Bei jeder 1 wechselt der Zustand, bei einer 0 bleibt er. Deshalb reichen zwei Zustände, auch bei beliebig langer Eingabe.
Ein Fahrkartenautomat mit Münzen von 1 € und 2 € und einem Ticket für 3 € braucht die Zustände 0 €, 1 € und 2 €. Die Zustände zeigen, wie viel Geld schon drin ist, solange noch kein Ticket kommt. Beispiele: 0 € –1 €→ 1 €, 0 € –2 €→ 2 €, 1 € –1 €→ 2 €. Sobald 3 € oder mehr eingeworfen sind, wird das Ticket ausgegeben und der Automat geht zurück zu 0 €: 1 € –2 €→ Ticket → 0 €, 2 € –1 €→ Ticket → 0 € und auch 2 € –2 €→ Ticket (4 € eingeworfen) → 0 €. Ein Zustand bedeutet hier: „so viel Geld ist schon drin“.
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…
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“).
- a) Entwickle den Automaten: Nenne die Zustände und stelle die Übergangstabelle auf.
- 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. a) Entwickle den Automaten mit möglichst wenig…
Ein Automat verarbeitet Binärzahlen (Zeichen 0 und 1) und soll erkennen, ob die Anzahl der gelesenen Einsen gerade ist.
- a) Entwickle den Automaten mit möglichst wenig Zuständen. Lege Startzustand und Endzustand fest und gib die Übergangstabelle an.
- b) Prüfe die Eingaben 10110 und 0000.
- 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…
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.
- a) Bestimme die nötigen Zustände.
- b) Stelle die Übergangstabelle für die Eingaben „1 €“ und „2 €“ auf.
- 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). a)…
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).
- a) Entwickle den Automaten mit Zuständen und Übergangstabelle.
- b) Teste ihn mit
1101und10101und gib jeweils die Zustandsfolge an.
- c) Erkläre, was jeder Zustand „sich merkt“.
Vorne im Text hast du gefragt, wie man die Schranke genau beschreibt: mit zwei Zuständen, zwei Übergängen und einem Startzustand, also mit einem Zustandsübergangsdiagramm.
Auf einen Blick
-
Ein Automat hat endlich viele Zustände, einen Startzustand und Regeln für Übergänge.
-
Im Zustandsübergangsdiagramm sind Zustände Kreise und Übergänge beschriftete Pfeile; Endzustände sind doppelt gezeichnet.
-
Die Übergangstabelle enthält zu jedem Zustand und jeder Eingabe den Folgezustand, vollständig.
-
Eine Eingabefolge liest du Zeichen für Zeichen; ein Wort wird akzeptiert, wenn der Automat danach im Endzustand ist.
-
Beim Entwickeln fragst du: Was muss sich der Automat merken? Jede Erinnerung ist ein Zustand. Danach testest du mit Beispielen.