Der Paritätsbit-Erzeuger
14 BEAFB I–IIBei der Übertragung von Daten hängt ein Sender an jeden Block ein Paritätsbit an, sodass die Anzahl der Einsen insgesamt gerade ist. Der Empfänger kann so einzelne Übertragungsfehler erkennen. Der abgebildete Mealy-Automat liest die Datenbits eines Blocks und gibt nach jedem Bit das Paritätsbit für den bisher gelesenen Teil aus.
- Nennen Sie das Eingabealphabet \(\Sigma\), das Ausgabealphabet \(\Omega\) und den Startzustand des Automaten. Geben Sie die Bedeutung der Zustände an. (3 BE)
- Bestimmen Sie mit einem Ablaufprotokoll das Ausgabewort zur Eingabe
1011001und geben Sie das Paritätsbit dieses Blocks an. (4 BE) - Erläutern Sie, warum die Ausgabe am Übergang und nicht im Zustand steht, und warum der Automat keine Endzustände besitzt. (3 BE)
- Der Sender soll künftig jedes Datenbit unverändert weitergeben und erst beim zusätzlichen Eingabezeichen
s(Blockende) das Paritätsbit ausgeben; danach beginnt ein neuer Block. Erweitern Sie den Automaten entsprechend und geben Sie das Ausgabewort zur Eingabe1011san. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
s braucht jeder Zustand einen neuen Pfeil zurück zum Blockanfang.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
\(\Sigma=\{0,\,1\}\), \(\Omega=\{0,\,1\}\), Startzustand z0.
z0: Bisher wurde eine gerade Anzahl Einsen gelesen. z1: Bisher wurde eine ungerade Anzahl Einsen gelesen. Nur eine 1 wechselt den Zustand.
Erwartungshorizont zu Aufgabe b)
| Schritt | Zustand | Eingabe | Ausgabe | Folgezustand |
|---|---|---|---|---|
| 1 | z0 | 1 | 1 | z1 |
| 2 | z1 | 0 | 1 | z1 |
| 3 | z1 | 1 | 0 | z0 |
| 4 | z0 | 1 | 1 | z1 |
| 5 | z1 | 0 | 1 | z1 |
| 6 | z1 | 0 | 1 | z1 |
| 7 | z1 | 1 | 0 | z0 |
Ausgabewort 1101110. Das Paritätsbit ist die letzte Ausgabe: 0. Kontrolle: 1011001 enthält vier Einsen — gerade, also Paritätsbit 0.
Erwartungshorizont zu Aufgabe c)
Aus z1 führen Übergänge mit den Ausgaben 1 (bei Eingabe 0) und 0 (bei Eingabe 1). Die Ausgabe hängt also vom Zustand und vom gelesenen Zeichen ab und gehört deshalb an den Pfeil (Notation e / a).
Endzustände entscheiden beim DEA über Annehmen oder Ablehnen. Der Mealy-Automat übersetzt dagegen ein Eingabewort in ein Ausgabewort; es gibt nichts anzunehmen oder abzulehnen.
Erwartungshorizont zu Aufgabe d)
\(\Sigma=\{0,\,1,\,s\}\). Datenbits: e / e (Weitergabe), Zustandswechsel wie bisher. Blockende: in z0 s / 0, in z1 s / 1, jeweils nach z0.
Eingabe 1011s: z0 → z1 → z1 → z0 → z1 → z0, Ausgabewort 10111 (Daten 1011 und Paritätsbit 1).
Der Fahrkartenautomat
17 BEAFB II–IIIEin Fahrkartenautomat im Stadtbus verkauft nur eine Kurzstreckenkarte zu 2,00 €. Er nimmt Münzen zu 50 ct, 1 € und 2 € an. Sobald das eingeworfene Guthaben 2,00 € erreicht oder überschreitet, gibt er die Karte aus und zahlt den Überschuss mit möglichst wenigen Münzen zurück. Danach ist das Guthaben wieder 0.
Modellieren Sie den Automaten als Mealy-Automaten mit den Zuständen 0 ct, 50 ct, 100 ct und 150 ct (Guthaben), \(\Sigma=\{50,\,100,\,200\}\) (Münzwert in Cent) und \(\Omega=\{\text{Karte},\,50\text{ ct},\,1\text{ €}\}\). Ausgaben dürfen Wörter über \(\Omega\) sein, z. B. „Karte, 50 ct“.
- Erstellen Sie die vollständige Übergangstabelle mit Folgezustand und Ausgabe. (5 BE)
- Ermitteln Sie mithilfe eines Ablaufprotokolls die Ausgabe des Automaten, wenn nacheinander die Münzen 50 ct, 1 €, 2 €, 1 €, 1 € eingeworfen werden. (4 BE)
- Der Automat erhält eine Abbruchtaste
x, die das bisherige Guthaben zurückzahlt. Entwickeln Sie die zusätzlichen Übergänge und begründen Sie, warum dafür keine neuen Zustände nötig sind. (4 BE) - Die Verkehrsbetriebe planen, den Preis auf 2,70 € zu erhöhen und zusätzlich 10-ct- und 20-ct-Münzen anzunehmen. Diskutieren Sie, ob die Modellierung als Mealy-Automat dann noch sinnvoll ist. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Zustand | 50 | 100 | 200 |
|---|---|---|---|
| 0 ct | 50 ct / ε | 100 ct / ε | 0 ct / Karte |
| 50 ct | 100 ct / ε | 150 ct / ε | 0 ct / Karte, 50 ct |
| 100 ct | 150 ct / ε | 0 ct / Karte | 0 ct / Karte, 1 € |
| 150 ct | 0 ct / Karte | 0 ct / Karte, 50 ct | 0 ct / Karte, 1 €, 50 ct |
(→ Startzustand; Feld: Folgezustand / Ausgabe)
Erwartungshorizont zu Aufgabe b)
| Schritt | Zustand | Eingabe | Ausgabe | Folgezustand |
|---|---|---|---|---|
| 1 | 0 ct | 50 | ε | 50 ct |
| 2 | 50 ct | 100 | ε | 150 ct |
| 3 | 150 ct | 200 | Karte, 1 €, 50 ct | 0 ct |
| 4 | 0 ct | 100 | ε | 100 ct |
| 5 | 100 ct | 100 | Karte | 0 ct |
Ausgabewort: „Karte, 1 €, 50 ct, Karte“. Kontrolle: Eingeworfen wurden 5,50 €; zwei Karten (4,00 €) und 1,50 € Rückgeld ergeben 5,50 €.
Erwartungshorizont zu Aufgabe c)
| Zustand | x |
|---|---|
| 0 ct | 0 ct / ε |
| 50 ct | 0 ct / 50 ct |
| 100 ct | 0 ct / 1 € |
| 150 ct | 0 ct / 1 €, 50 ct |
Der Zustand speichert bereits das gesamte Guthaben, also genau die Information, die für die Rückzahlung nötig ist. Nach dem Abbruch ist das Guthaben 0 — dieser Zustand existiert schon. Es kommen nur vier Übergänge hinzu, \(\Sigma\) wird zu \(\{50,\,100,\,200,\,x\}\).
Erwartungshorizont zu Aufgabe d)
Pro: Das Modell bleibt korrekt und endlich. Alle möglichen Guthaben unter 2,70 € in 10-ct-Schritten ergeben 27 Zustände, mit fünf Münzsorten \(27\cdot5=135\) Übergänge. Jeder Übergang lässt sich systematisch berechnen und testen.
Contra: Ein solcher Graph ist nicht mehr übersichtlich zeichenbar; Ausgabewörter wie „Karte, 1 €, 20 ct, 10 ct“ werden lang. Außerdem bildet das Modell weder den Münzvorrat für Wechselgeld noch Fehlerfälle ab; dafür bräuchte es weitere Zustandsinformationen.
Ergebnis: Als Entwurfs- und Testmodell bleibt der Mealy-Automat sinnvoll, zur Darstellung eignet sich eine Tabelle; implementiert wird man das Guthaben eher als Zahl in einer Variablen.