Automaten — Zustände und Übergänge

Automata — States and Transitions

Informatik Klasse 4 13 Aufgaben

InformatikInformatisches Denken

Ein Automat hat wenige Zustände und wechselt bei einer Eingabe nach einer festen Regel in den nächsten: die Ampel, eine Tür mit Schlüssel, ein Saftautomat, der Münzen zählt, eine Schatzsuche von Insel zu Insel (die Endliche-Automaten-Aktivität aus CS Unplugged, Bell, Witten & Fellows). Die Kinder lesen eine Zustandstabelle und sagen, in welchem Zustand der Automat nach einer Folge von Eingaben ist. Das ist der Inhaltsbereich „Sprachen und Automaten“ der GI-Empfehlungen für den Primarbereich (2019). Gegen drei Fehler: Zustand wird mit Eingabe oder Ausgabe verwechselt („der Zustand ist ‚Münze‘“), der Automat merkt sich die ganze Vorgeschichte statt nur seinen Zustand, und ein Übergang wird als Folge von Schritten statt als eine Regel pro Zustand und Eingabe gelesen. Die spätere Formalisierung (Hromkovič, Sek I) und endliche Automaten in Klasse 12 bauen darauf auf; ein Zustand ist eine Variable (Klasse 7).

Leicht

Multiple Choice #1 12s ▶ Testen

Ampel: rot → rotgelb → grün → gelb → rot. Jeder Takt führt einen Pfeil weiter. Zustand: rot. Eingaben: 1 Takt. In welchem Zustand ist der Automat danach?

● rotgelb
○ grün
○ gelb

Ein Takt ist genau ein Pfeil: von rot nach rotgelb. Rotgelb ist ein eigener Zustand, den darfst du nicht überspringen. Gelb käme nur, wenn du den Pfeil rückwärts liest.

Wahr / Falsch #2 15s ▶ Testen

Ampel: rot → rotgelb → grün → gelb → rot. Jeder Takt führt einen Pfeil weiter. Zustand: gelb. Eingaben: 2 Takte. Danach ist der Automat im Zustand ‚rotgelb‘.

✓ Wahr

Von gelb führt der Pfeil zurück zu rot (1), dann weiter zu rotgelb (2). Die Ampel läuft im Kreis.

Wahr / Falsch #3 15s ▶ Testen

Saftautomat: Jede 1-€-Münze führt einen Zustand weiter (0 € → 1 € → 2 €). Taste bei 2 €: Saft, dann 0 €. Zustand: 2 €. Eingaben: Taste. Danach ist der Automat im Zustand ‚Saft‘.

✓ Falsch

Saft ist das, was herauskommt — kein Zustand. Der Automat ist danach im Zustand 0 €.

Wahr / Falsch #4 18s ▶ Testen

Tür — offen: Schließen → zu. zu: Schlüssel → abgeschlossen, Klinke → offen. abgeschlossen: Schlüssel → zu. Zustand: offen. Eingaben: Schließen, Schlüssel. Danach ist der Automat im Zustand ‚Schlüssel‘.

✓ Falsch

Schlüssel ist eine Eingabe, kein Zustand. Offen → zu → abgeschlossen. Der Zustand ist danach abgeschlossen.

Multiple Choice #5 20s ▶ Testen

Schatzkarte — Hafen: A → Nord, B → Süd. Nord: A → Schatz, B → Hafen. Süd: A → Hafen, B → Nord. Zustand: Hafen. Eingaben: B, B. In welchem Zustand ist der Automat danach?

● Nord
○ Süd
○ Hafen

Vom Hafen fährt B nach Süd. Jetzt gilt die Zeile von Süd: B fährt nach Nord. B bedeutet nicht immer Süd — es kommt auf die Insel an, auf der du gerade bist.

Mittel

Lückentext #1 20s ▶ Testen

Ampel: rot → rotgelb → grün → gelb → rot. Jeder Takt führt einen Pfeil weiter. Zustand: grün. Eingaben: 6 Takte. In welchem Zustand ist der Automat danach? ___

✓ Antwort: rot

Pfeil für Pfeil: grün → gelb (1) → rot (2) → rotgelb (3) → grün (4) → gelb (5) → rot (6).

Multiple Choice #2 20s ▶ Testen

Saftautomat: Jede 1-€-Münze führt einen Zustand weiter (0 € → 1 € → 2 €). Taste bei 2 €: Saft, dann 0 €. Zustand: 0 €. Eingaben: Münze, Münze, Taste. In welchem Zustand ist der Automat danach?

● 0 €
○ 2 €
○ 1 €

Münze: 1 €, Münze: 2 €, Taste: Saft kommt, und der Automat steht wieder auf 0 €. Er merkt sich nicht, wie viele Münzen schon eingeworfen wurden, nur seinen Zustand. Die Taste führt nicht einen Pfeil zurück, sondern gleich auf 0 €.

Multiple Choice #3 25s ▶ Testen

Tür — offen: Schließen → zu. zu: Schlüssel → abgeschlossen, Klinke → offen. abgeschlossen: Schlüssel → zu, Klinke → bleibt. Zustand: abgeschlossen. Eingaben: Klinke, Schlüssel. In welchem Zustand ist der Automat danach?

● zu
○ offen
○ abgeschlossen

Jede Regel gilt nur in ihrem Zustand. Klinke bei abgeschlossen: Die Tür bleibt abgeschlossen. Schlüssel bei abgeschlossen: zu. Die Klinke öffnet nur, wenn die Tür zu ist, und der Schlüssel schließt nicht immer ab.

Wahr / Falsch #4 20s ▶ Testen

Drehkreuz — gesperrt: Münze → frei. frei: Durchgehen → gesperrt. Sonst bleibt der Zustand. Zustand: gesperrt. Eingaben: Münze, Münze, Durchgehen. Danach ist der Automat im Zustand ‚frei‘.

✓ Falsch

Gesperrt → frei. Die zweite Münze bei frei: Es bleibt frei. Durchgehen: gesperrt. Das Drehkreuz merkt sich nicht, dass zwei Münzen kamen — es kennt nur frei oder gesperrt.

Wahr / Falsch #5 18s ▶ Testen

Lampe: Jeder Druck wechselt zwischen an und aus. Beide Lampen sind aus. Lea drückt 3-mal, Tim 5-mal. Danach ist Tims Lampe im selben Zustand wie Leas.

✓ Wahr

Lea: an, aus, an. Tim: an, aus, an, aus, an. Beide sind an. Was vorher passiert ist, sieht man der Lampe nicht an — sie kennt nur ihren Zustand.

Wahr / Falsch #6 18s ▶ Testen

Schatzkarte — Hafen: A → Nord, B → Süd. Nord: A → Schatz, B → Hafen. Süd: A → Hafen, B → Nord. Zustand: Nord. Eingaben: B, A. Danach ist der Automat im Zustand ‚Nord‘.

✓ Wahr

Von Nord fährt B zum Hafen, vom Hafen fährt A nach Nord. Du bist wieder dort, wo du angefangen hast.

Lückentext #7 22s ▶ Testen

Schatzkarte — Wald: X → Fluss, Y → Berg. Berg: X → Wald, Y → Fluss. Fluss: X → Berg, Y → Schatz. Zustand: Wald. Eingaben: Y, Y, Y. In welchem Zustand ist der Automat danach? ___

✓ Antwort: Schatz

Wald, Y → Berg. Berg, Y → Fluss. Fluss, Y → Schatz. Dreimal Y, aber jedes Mal gilt die Zeile der Insel, auf der du gerade bist.

Lückentext #8 22s ▶ Testen

Fahrstuhl: Zustände EG, 1, 2. Hoch: ein Stock höher, Runter: ein Stock tiefer. Ganz oben oder unten bleibt er stehen. Zustand: EG. Eingaben: Runter, Runter, Hoch, Hoch. In welchem Zustand ist der Automat danach? ___

✓ Antwort: 2

Runter bei EG: Er bleibt im EG, zweimal. Dann Hoch: 1, Hoch: 2. Du darfst die Eingaben nicht einfach verrechnen — jede wirkt im Zustand, in dem der Fahrstuhl gerade ist.