Caesar mit Wechselschritt
14 BEAFB I–IIBei der Caesar-Verschlüsselung wird jeder Buchstabe um eine feste Zahl von Stellen im Alphabet verschoben; nach Z geht es mit A weiter. Der abgebildete Mealy-Automat verschiebt um 3 Stellen. Es gilt \(\Sigma=\Omega=\{A,\,B,\,\dots,\,Z\}\).
Die Beschriftung x / x+k fasst 26 Übergänge zusammen: Für jeden Buchstaben x wird der um k Stellen verschobene Buchstabe ausgegeben.
- Wenden Sie den abgebildeten Automaten auf das Wort
ZUGan. (2 BE) - Um die Verschlüsselung sicherer zu machen, soll abwechselnd um 1 und um 2 Stellen verschoben werden, beginnend mit 1. Erstellen Sie einen Mealy-Automaten für dieses Verfahren. (4 BE)
- Stellen Sie die Verschlüsselung des Wortes
ZOOmit Ihrem Automaten in einem Ablaufprotokoll dar. (4 BE) - Begründen Sie, dass sich das Verfahren aus b) nicht mit einem Mealy-Automaten mit nur einem Zustand umsetzen lässt, und geben Sie an, wie ein Automat zum Entschlüsseln aussieht. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Z → C, U → X, G → J: Ausgabewort CXJ. Der Automat bleibt die ganze Zeit in z0.
Erwartungshorizont zu Aufgabe b)
z0: „als Nächstes um 1 verschieben“, z1: „als Nächstes um 2 verschieben“. Jeder Buchstabe wechselt den Zustand.
Erwartungshorizont zu Aufgabe c)
| Schritt | Zustand | Eingabe | Ausgabe | Folgezustand |
|---|---|---|---|---|
| 1 | z0 | Z | A | z1 |
| 2 | z1 | O | Q | z0 |
| 3 | z0 | O | P | z1 |
Ausgabewort AQP.
Erwartungshorizont zu Aufgabe d)
Mit nur einem Zustand hängt die Ausgabe allein vom gelesenen Buchstaben ab — derselbe Buchstabe würde immer gleich verschlüsselt. In ZOO wird das erste O aber zu Q, das zweite zu P. Der Automat muss sich also die Position (gerade/ungerade) merken: zwei Zustände.
Entschlüsseln: gleicher Graph, Beschriftungen x / x−1 (z0 → z1) und x / x−2 (z1 → z0). Aus AQP wird wieder ZOO.
Der Morse-Taster
18 BEAFB II–IIIEin Morse-Taster wird in festen Zeittakten abgefragt: d bedeutet „in diesem Takt gedrückt“, p „in diesem Takt nicht gedrückt“. Ein Mealy-Automat soll daraus Morsezeichen erzeugen: War die Taste genau einen Takt gedrückt, wird ein Punkt · ausgegeben, bei zwei oder mehr Takten ein Strich –. Das Zeichen wird im ersten Pausentakt nach dem Drücken ausgegeben, in allen anderen Takten wird nichts ausgegeben.
Es gilt \(\Sigma=\{d,\,p\}\) und \(\Omega=\{\cdot,\,–,\,/\}\); der Taster ist zu Beginn nicht gedrückt.
- Ermitteln Sie ohne Automaten die Soll-Ausgabe zur Eingabe
dpdddppdpund geben Sie an, in welchen Takten eine Ausgabe erfolgt. (3 BE) - Entwerfen Sie einen Mealy-Automaten für den Morse-Taster und geben Sie die Bedeutung der Zustände an. (5 BE)
- Folgen nach einem Morsezeichen drei Pausentakte hintereinander (einschließlich des Pausentakts, der das Zeichen beendet), ist der Buchstabe zu Ende; dann soll im dritten Pausentakt zusätzlich
/ausgegeben werden. Erweitern Sie Ihren Automaten und prüfen Sie ihn mit einem Ablaufprotokoll zur Eingabedpdddppdppp. (6 BE) - Im internationalen Morsecode dauert ein Strich drei Punktlängen, zwischen Buchstaben liegen drei, zwischen Wörtern sieben Pausentakte. Bewerten Sie, ob ein Mealy-Automat geeignet ist, die Eingaben eines Menschen an einer Morsetaste zuverlässig zu übersetzen. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Blöcke: d (1 Takt) → Punkt im 2. Takt; ddd (3 Takte) → Strich im 6. Takt; d → Punkt im 9. Takt. Soll-Ausgabe: · – · (der Buchstabe R).
Erwartungshorizont zu Aufgabe b)
z0: Taste nicht gedrückt; z1: seit genau einem Takt gedrückt; z2: seit mindestens zwei Takten gedrückt. Kontrolle mit dpdddppdp: Ausgaben · (Takt 2), – (Takt 6), · (Takt 9) — wie in a).
Erwartungshorizont zu Aufgabe c)
z3: Zeichen ausgegeben, ein Pausentakt; z4: zwei Pausentakte. Erst der dritte Pausentakt erzeugt / und führt nach z0, wo weitere Pausen nichts ausgeben.
| Schritt | Zustand | Eingabe | Ausgabe | Folgezustand |
|---|---|---|---|---|
| 1 | z0 | d | ε | z1 |
| 2 | z1 | p | · | z3 |
| 3 | z3 | d | ε | z1 |
| 4 | z1 | d | ε | z2 |
| 5 | z2 | d | ε | z2 |
| 6 | z2 | p | – | z3 |
| 7 | z3 | p | ε | z4 |
| 8 | z4 | d | ε | z1 |
| 9 | z1 | p | · | z3 |
| 10 | z3 | p | ε | z4 |
| 11 | z4 | p | / | z0 |
Ausgabewort · – · /.
Erwartungshorizont zu Aufgabe d)
Alle Regeln verlangen nur Zählen bis zu festen Grenzen (höchstens sieben Takte). Das gelingt mit endlich vielen Zuständen: Wortabstände brauchen z. B. einige Zustände mehr für die Pausen 4 bis 7. Formal ist ein Mealy-Automat also geeignet.
Menschen drücken aber nicht taktgenau: Ein Strich dauert mal zwei, mal vier Takte. Ein starrer Automat mit genau festgelegten Grenzen übersetzt dann falsch. Man muss Toleranzbereiche festlegen (z. B. 1 Takt = Punkt, ab 2 Takten = Strich, wie in b) oder das Tempo anpassen — letzteres übersteigt ein festes Modell.
Urteil: Für eine gleichmäßige, maschinell erzeugte Eingabe ist der Mealy-Automat gut geeignet; für menschliche Eingaben nur mit großzügigen Toleranzen.