Die Parkhausschranke
13 BEAFB I–IIDie Schranke an der Einfahrt eines Parkhauses wird von einer Steuerung mit drei Zuständen gelenkt: zu (Schranke geschlossen), offen (Schranke geöffnet) und Störung (Alarm an der Leitstelle). Die Steuerung reagiert auf vier Eingaben:
T: gültiges Ticket gezogen · U: ungültige Karte eingesteckt · L: Lichtschranke meldet ein durchfahrendes Fahrzeug · S: Servicetaste des Personals.
Beim Einschalten ist die Schranke geschlossen. Die Abbildung zeigt den Zustandsgraphen der Steuerung.
- Geben Sie den Startzustand sowie alle Übergänge an, die aus dem Zustand offen herausführen oder in ihm bleiben. (3 BE)
- Stellen Sie die Verarbeitung der Eingabefolge U, T, L, L, S, T in einem Protokoll (Schritt, Zustand, Eingabe, Folgezustand) dar und geben Sie den Zustand am Ende an. (4 BE)
- Beschreiben Sie, wie die Steuerung auf die Eingabe L in jedem der drei Zustände reagiert, und deuten Sie dies im Sachzusammenhang. (3 BE)
- Ein Autofahrer zieht für sich und seinen nachfolgenden Bekannten zwei gültige Tickets hintereinander. Begründen Sie mithilfe des Graphen, dass trotzdem nur ein Fahrzeug ohne Alarm einfahren kann. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Startzustand: zu.
Aus offen: T → offen, U → offen, S → offen (Schleife), L → zu.
Damit sind alle vier Eingaben für offen erfasst — der Graph ist an dieser Stelle vollständig.
Erwartungshorizont zu Aufgabe b)
| Schritt | Zustand | Eingabe | Folgezustand |
|---|---|---|---|
| 1 | zu | U | zu |
| 2 | zu | T | offen |
| 3 | offen | L | zu |
| 4 | zu | L | Störung |
| 5 | Störung | S | zu |
| 6 | zu | T | offen |
Zustandsfolge: zu → zu → offen → zu → Störung → zu → offen. Am Ende ist die Schranke offen.
Erwartungshorizont zu Aufgabe c)
- offen → zu: Das berechtigte Fahrzeug ist durchgefahren, die Schranke schließt.
- zu → Störung: Bei geschlossener Schranke wird ein Fahrzeug gemeldet — jemand fährt ohne Berechtigung durch oder die Lichtschranke ist gestört; es wird Alarm ausgelöst.
- Störung → Störung: Weitere Meldungen ändern nichts; nur das Personal (S) beendet den Alarm.
Dieselbe Eingabe hat also drei verschiedene Wirkungen — entscheidend ist der aktuelle Zustand.
Erwartungshorizont zu Aufgabe d)
Zustandsfolge: zu \(\xrightarrow{T}\) offen \(\xrightarrow{T}\) offen \(\xrightarrow{L}\) zu \(\xrightarrow{L}\) Störung.
Das zweite T ist eine Schleife auf offen: Der Zustand speichert nur „offen“, nicht die Anzahl bezahlter Tickets. Nach dem ersten Fahrzeug schließt die Schranke; das zweite löst im Zustand zu den Alarm aus.
Der Fahrstuhl
16 BEAFB II–IIIEin Fahrstuhl in einem Wohnhaus bedient das Erdgeschoss und zwei Obergeschosse. In der Kabine gibt es die Tasten e, 1 und 2. Drückt man eine Taste, fährt der Fahrstuhl ohne Zwischenhalt in die gewählte Etage; die Taste der aktuellen Etage bewirkt nichts. Weitere Tastendrücke während der Fahrt werden ignoriert. Beim Einschalten steht der Fahrstuhl im Erdgeschoss.
Die Zustände heißen E, O1 und O2 nach der Etage, in der der Fahrstuhl steht.
- Zeichnen Sie den vollständigen Zustandsgraphen der Fahrstuhlsteuerung. (4 BE)
- Über der Kabinentür soll ein Pfeil anzeigen, ob der Fahrstuhl zuletzt aufwärts (↑) oder abwärts (↓) gefahren ist. Erweitern Sie den Graphen so, dass jeder Zustand die Richtung der letzten Fahrt eindeutig festlegt. Verwenden Sie dabei möglichst wenige Zustände. (5 BE)
- Eine Mitschülerin behauptet: „Für die Richtungsanzeige braucht man für jede Etage einen Zustand ‚aufwärts‘ und einen ‚abwärts‘, also sechs Zustände.“ Überprüfen Sie diese Aussage. (3 BE)
- Echte Fahrstühle speichern mehrere Fahrtwünsche gleichzeitig, z. B. „erst 2, dann e“, und arbeiten sie nacheinander ab. Beurteilen Sie, ob sich ein solcher Fahrstuhl für ein Haus mit \(n\) Etagen noch mit endlich vielen Zuständen modellieren lässt. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Aus jedem Zustand führt jede Taste in die Etage der Taste; insgesamt 9 Übergänge, davon 3 Schleifen.
Erwartungshorizont zu Aufgabe b)
Nur das 1. OG wird von unten und von oben erreicht; es wird in 1↑ und 1↓ aufgeteilt. E bedeutet „abwärts“ (bzw. noch keine Fahrt), 2 immer „aufwärts“. Vier Zustände, \(4\cdot3=12\) Übergänge; die Schleifen behalten die Richtung, weil keine Fahrt stattfindet.
Erwartungshorizont zu Aufgabe c)
Die Aussage ist falsch. „E aufwärts“ ist unerreichbar (unter E gibt es keine Etage), ebenso „O2 abwärts“. Ein Automat mit sechs Zuständen funktioniert zwar, enthält aber zwei überflüssige Zustände. Nötig sind nur Zustände für Situationen, die tatsächlich unterschieden werden müssen — hier vier.
Erwartungshorizont zu Aufgabe d)
Ja: Jede Etage ist entweder angefordert oder nicht. Mit aktueller Etage (\(n\) Möglichkeiten), Richtung (2) und der Menge der offenen Wünsche (\(2^n\) Teilmengen) gibt es höchstens \(n\cdot2\cdot2^n\) Zustände — endlich viele.
Die Zahl wächst aber exponentiell (bei \(n=10\) schon über 20 000). Der Zustandsgraph ist dann nicht mehr zeichenbar; man beschreibt die Zustände besser durch Variablen (Etage, Richtung, Wunschliste) in einem Programm. Das Modell bleibt korrekt, ist aber nur für kleine Häuser als Graph sinnvoll.