Automaten: Zustände und Zustandsübergänge
Du stehst an einer Ampel. Sie zeigt Rot. Nach einiger Zeit leuchtet Rot und Gelb zusammen, dann Grün, dann Gelb, dann wieder Rot. Die Ampel denkt nicht. Sie folgt festen Regeln. Aber woher weiß sie, was als Nächstes kommt? Sie muss sich merken, welches Licht gerade leuchtet.
Ein Getränkeautomat ist ähnlich. Wirfst du die erste Münze ein, passiert nichts. Erst bei der zweiten kommt die Flasche. Er muss sich also merken, dass schon eine Münze drin ist.
Du lernst, wie man solche Geräte mit einer Zeichnung und einer Tabelle beschreibt und ihr Verhalten Schritt für Schritt nachspielt.
Automat und Zustand
Ein Automat ist ein Gerät, das nach festen Regeln auf etwas reagiert. In der Informatik meint man damit auch den Plan, der die Regeln eines solchen Geräts beschreibt.
Ein Automat hat endlich viele Zustände. Der Zustand ist das, was sich der Automat gerade merkt. Er ist immer in genau einem Zustand. Der Zustand, in dem er beginnt, heißt Startzustand.
Die Ampel hat vier Zustände: Rot, Rot-Gelb, Grün und Gelb. Es leuchtet immer genau eine dieser Kombinationen. Der Startzustand ist Rot.
Ereignis, Aktion und Zustandsänderung
Drei Wörter beschreiben, was ein Automat tut:
- Ein Ereignis passiert von außen. Beispiele: Münze einwerfen, Taste drücken, Zeit ist um.
- Eine Aktion tut der Automat selbst. Beispiele: Flasche ausgeben, Licht einschalten.
- Eine Zustandsänderung (auch Übergang) ist der Wechsel in einen anderen Zustand. Der Automat kann auch im selben Zustand bleiben.
Der Ablauf ist immer gleich: Der Automat steht in einem Zustand, und ein Ereignis tritt ein. Dann führt er die Aktion aus und wechselt in den neuen Zustand. Die Regeln liegen vorher fest. Bei gleichem Zustand und gleichem Ereignis tut er darum immer dasselbe.
Bei der Ampel: Zustand Rot, Ereignis „Zeit ist um“, Aktion „Gelb dazuschalten“, neuer Zustand Rot-Gelb.
Zustandsgraph und Automatentafel
Einen Automaten beschreibst du auf zwei Arten.
Der Zustandsgraph ist eine Zeichnung. Jeder Zustand ist ein Kreis mit seinem Namen. Jeder Übergang ist ein Pfeil vom alten zum neuen Zustand. Am Pfeil steht „Ereignis / Aktion“. Auf den Startzustand zeigt ein Pfeil, der von außen kommt.
Die Automatentafel ist eine Tabelle. Jeder Zustand bekommt eine Zeile, jedes Ereignis eine Spalte. In jedem Feld steht der neue Zustand, bei Bedarf mit der Aktion. Kein Feld darf leer bleiben, damit der Automat in jeder Lage weiß, was er tut.
Einen Getränkeautomaten entwickeln
Einen Getränkeautomaten entwickeln
Ein Automat verkauft Flaschen für 1 Euro. Er nimmt nur 50-Cent-Münzen. Es gibt eine Rückgabetaste. Wir entwickeln das Modell in vier Schritten.
Das sind die Schritte:
- Schritt 1, Zustände: Was muss sich der Automat merken? Wie viel Geld schon drin ist, nämlich 0 Cent oder 50 Cent. Bei der zweiten Münze gibt er die Flasche aus, mehr braucht er nicht. Die Zustände heißen „Leer“ (Startzustand) und „Halb“.
- Schritt 2, Ereignisse: „Münze“ und „Rückgabe“.
- Schritt 3, Übergänge: Gehe jede Kombination aus Zustand und Ereignis durch. „Leer“ und „Münze“: Er merkt sich die Münze und geht nach „Halb“. „Halb“ und „Münze“: Es liegt 1 Euro drin. Er gibt die Flasche aus und geht nach „Leer“. „Leer“ und „Rückgabe“: Es gibt nichts zurückzugeben, er bleibt in „Leer“. „Halb“ und „Rückgabe“: Er gibt 50 Cent zurück und geht nach „Leer“.
- Schritt 4, Tafel:
| Zustand | Ereignis „Münze“ | Ereignis „Rückgabe“ |
|---|---|---|
| Leer | Halb | Leer |
| Halb | Leer, Aktion: Flasche ausgeben | Leer, Aktion: 50 Cent zurückgeben |
Der Zustandsgraph hat zwei Kreise, „Leer“ mit dem Startpfeil und „Halb“. Er hat vier Pfeile:
- Von Leer nach Halb, Beschriftung „Münze“.
- Von Halb nach Leer, Beschriftung „Münze / Flasche ausgeben“.
- Von Halb nach Leer, Beschriftung „Rückgabe / 50 Cent zurückgeben“.
- Von Leer zu sich selbst, Beschriftung „Rückgabe“.
Den Automaten nachspielen
Den Automaten nachspielen
Der Automat steht in „Leer“. Nacheinander treten diese Ereignisse ein: Münze, Rückgabe, Münze, Münze, Münze. Wir lesen jeden Schritt aus der Tafel ab.
| Schritt | Zustand vorher | Ereignis | Aktion | Zustand nachher |
|---|---|---|---|---|
| 1 | Leer | Münze | keine | Halb |
| 2 | Halb | Rückgabe | 50 Cent zurückgeben | Leer |
| 3 | Leer | Münze | keine | Halb |
| 4 | Halb | Münze | Flasche ausgeben | Leer |
| 5 | Leer | Münze | keine | Halb |
Am Ende steht der Automat in „Halb“. Eine Probe zeigt, dass das stimmt: Es wurden 4 Münzen eingeworfen, das sind 4 · 50 = 200 Cent. Davon gingen 50 Cent zurück und 100 Cent für die Flasche. Es bleiben 200 − 50 − 100 = 50 Cent im Automaten. Das passt zum Zustand „Halb“.
Ein Automat, der Bitfolgen prüft
Ein Automat, der Bitfolgen prüft
Ein Automat kann auch eine Folge von Zeichen prüfen. Das passt zur letzten Lektion: Eine Bildzeile aus Nullen und Einsen ist so eine Folge. Der Automat soll prüfen, ob in der Zeile nie zwei schwarze Pixel (zwei Einsen) direkt nebeneinander stehen.
Eine Folge von Zeichen, die er Zeichen für Zeichen liest, heißt hier Wort. Jedes gelesene Zeichen ist ein Ereignis. Eine Aktion gibt es nicht. Am Ende sagt der Automat nur „angenommen“ oder „abgelehnt“. Er hat drei Zustände:
- q0: Bisher ist alles in Ordnung, und das letzte Zeichen war eine 0 (oder es gab noch keines). Das ist der Startzustand.
- q1: Bisher ist alles in Ordnung, und das letzte Zeichen war eine 1.
- q_tot: Es kamen zwei Einsen hintereinander. Hier bleibt der Automat für immer, egal was noch kommt.
q0 und q1 sind Endzustände. Steht der Automat nach dem letzten Zeichen in einem Endzustand, ist das Wort angenommen. Sonst ist es abgelehnt. Im Zustandsgraph zeichnet man Endzustände als Doppelkreis. Das ist die Tafel:
| Zustand | liest 0 | liest 1 |
|---|---|---|
| q0 | q0 | q1 |
| q1 | q0 | q_tot |
| q_tot | q_tot | q_tot |
Wir spielen das Wort 10101 nach. Start in q0.
- Lies 1: Die Tafel sagt q1.
- Lies 0: q0.
- Lies 1: q1.
- Lies 0: q0.
- Lies 1: q1.
Das Wort ist zu Ende, und q1 ist ein Endzustand. Das Wort 10101 wird angenommen. Tatsächlich stehen darin nie zwei Einsen nebeneinander.
Zustand und Ereignis verwechseln
Zustand und Ereignis verwechseln
„Münze einwerfen ist ein Zustand des Automaten.“
Ein Zustand dauert an: Der Automat kann eine Weile darin bleiben, zum Beispiel in „Halb“. Ein Ereignis geschieht einmal von außen, zum Beispiel das Einwerfen der Münze. Das Ereignis löst den Wechsel von einem Zustand in einen anderen aus.
Felder der Tafel leer lassen
Felder der Tafel leer lassen
„Wenn man bei ‚Leer‘ die Rückgabetaste drückt, passiert nichts. Also trage ich in die Tafel nichts ein.“
Auch „nichts tun“ ist eine Regel: Der Automat bleibt in seinem Zustand und führt keine Aktion aus. Das trägst du ein. Ein leeres Feld hieße, dass der Automat in dieser Lage nicht weiß, was er tun soll.
Zusammenfassung
Ein Automat reagiert nach festen Regeln. Er hat endlich viele Zustände, ist immer in genau einem und beginnt im Startzustand.
Ein Ereignis kommt von außen. Eine Aktion führt der Automat aus. Bei einer Zustandsänderung wechselt er den Zustand oder bleibt im alten.
Der Zustandsgraph zeigt Zustände als Kreise und Übergänge als Pfeile mit „Ereignis / Aktion“.
Die Automatentafel hat eine Zeile je Zustand und eine Spalte je Ereignis. Kein Feld darf leer sein.
Zum Entwickeln suchst du die Zustände, sammelst die Ereignisse und gehst jede Kombination durch. Zum Simulieren spielst du die Ereignisse nacheinander durch.
Ein Automat kann Wörter prüfen. Steht er nach dem letzten Zeichen in einem Endzustand, wird das Wort angenommen, sonst abgelehnt.
Übungen
Ein Drehkreuz im Schwimmbad ist gesperrt. Du steckst deine Karte ein, und es gibt den Weg frei. Was ist hier das Ereignis?
Ein Automat hat 3 Zustände und kennt 2 Ereignisse. Wie viele Felder hat seine Automatentafel ohne die Kopfzeile und ohne die Spalte mit den Zustandsnamen?
Die Ampel aus der Lektion geht bei jedem Ereignis „Zeit ist um“ zum nächsten Zustand: Rot, Rot-Gelb, Grün, Gelb, dann wieder Rot. Sie startet bei Rot. In welchem Zustand steht sie nach 10-mal „Zeit ist um“?
Der Getränkeautomat aus der Lektion steht in „Leer“. Nacheinander treten diese Ereignisse ein: Münze, Münze, Rückgabe, Münze, Münze, Münze, Münze. Wie viele Flaschen gibt er aus?
Der Prüfer aus der Lektion liest das Wort 0110. Was passiert?
Im Flur hängt eine Lampe mit einem Taster. Jeder Druck auf den Taster schaltet das Licht um: Ist es aus, geht es an. Ist es an, geht es aus. Gib die Zustände, das Ereignis und die Automatentafel an.