Kennzeichen prüfen
AFB I–IIEin Parkhaus erkennt vereinfachte Kennzeichen über dem Alphabet Σ = {B, Z, -} (B für einen Buchstaben, Z für eine Ziffer). Gültig sind Wörter, die aus ein bis zwei Buchstaben, einem Bindestrich und mindestens einer Ziffer bestehen, z. B. B-ZZ oder BB-Z.
- Zeichnen Sie einen DEA, der genau die gültigen Kennzeichen akzeptiert. Der Fehlerzustand darf weggelassen werden, wenn Sie das vermerken.
- Wenden Sie Ihren Automaten auf
BB-ZZZ,BBB-ZundB-an. - Entwerfen Sie ein Struktogramm für
pruefe(k: Zeichenkette): Wahrheitswert, das Ihren Automaten umsetzt.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Zustand | B | Z | - |
|---|---|---|---|
| s0 (Start) | s1 | F | F |
| s1 | s2 | F | s3 |
| s2 | F | F | s3 |
| s3 | F | s4 | F |
| s4 (Ende) | F | s4 | F |
F = Fehlerzustand (alle Zeichen führen nach F). Darstellung als Zustandsgraph mit Start-Pfeil und Doppelkreis s4 erwartet.
Erwartungshorizont zu Aufgabe b)
BB-ZZZ: s0 s1 s2 s3 s4 s4 s4 → akzeptiert. BBB-Z: s0 s1 s2 F … → abgelehnt. B-: s0 s1 s3 → kein Endzustand, abgelehnt.
Erwartungshorizont zu Aufgabe c)
pruefe(k: Zeichenkette): Wahrheitswert
Die Folgezustände dürfen auch direkt mit verschachtelten Verzweigungen (je Zustand, je Zeichen) notiert werden.
Morse-Übersetzer als Mealy-Automat
AFB II–IIIEin Mealy-Automat liest Morsezeichen über Σ = {., -, /} und gibt Buchstaben aus Ω = {E, T, I, A, N, M} aus. „/“ schließt einen Buchstaben ab. Es gilt: . = E, - = T, .. = I, .- = A, -. = N, -- = M.
- Zeichnen Sie den Übergangsgraphen. Ausgaben entstehen nur beim Lesen von „/“.
- Wenden Sie den Automaten auf
.-/-./-/an und geben Sie die Ausgabe an. - Begründen Sie, warum ein endlicher Automat alle Morsebuchstaben übersetzen kann, obwohl er kein unbegrenztes Gedächtnis hat.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Start q (leer). Von q: . / ε → q., - / ε → q-. Von q.: . / ε → q.., - / ε → q.-, / / E → q. Von q-: . / ε → q-., - / ε → q--, / / T → q. Von q.., q.-, q-., q--: / / I, A, N, M → q. Weitere Zeichen nach zwei Signalen führen in einen Fehlerzustand (erläutert).
Erwartungshorizont zu Aufgabe b)
.-/ → A, -./ → N, -/ → T. Ausgabe: ANT.
Erwartungshorizont zu Aufgabe c)
Jeder Morsebuchstabe besteht aus höchstens vier (hier: zwei) Signalen, danach folgt „/“. Der Automat muss sich also nur endlich viele Anfänge merken — dafür reichen endlich viele Zustände. Nach „/“ beginnt er wieder im Startzustand. Unbegrenzt zählen muss er nie.