Mealy-Automaten entwickeln: Übungen – Informatik Grundkurs

A1

Der Weg zum Entwurf

AFB I

Stellen Sie das Vorgehen beim Entwickeln eines Mealy-Automaten, indem Sie die Schritte in die richtige Reihenfolge bringen.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1Eingabealphabet Σ und Ausgabealphabet Ω festlegen

2Mit Beispielpaaren (Eingabewort → Ausgabewort) festhalten, wann was ausgegeben wird

3Klären, was sich der Automat von der Vergangenheit merken muss — daraus die Zustände mit Bedeutung

4Den Startzustand passend zur Lage vor dem ersten Zeichen wählen

5Für jeden Zustand und jedes Zeichen Folgezustand und Ausgabe e / a festlegen

6Testeingaben durchlaufen und Ist- mit Soll-Ausgabe im Ablaufprotokoll vergleichen

Häufigster Fehler: gleich mit Kreisen und Pfeilen anfangen. Welche Zustände nötig sind, ergibt sich erst aus der Frage, was für die Ausgabe gemerkt werden muss. Und die wiederum setzt voraus, dass die gewünschte Ausgabe an Beispielen geklärt ist.

Ansatz: Am Anfang steht, womit der Automat arbeitet; am Ende steht die Kontrolle.

Weiter: Zustände kann man erst festlegen, wenn klar ist, was ausgegeben werden soll.

A2

Stimmt das? — Entwurfsregeln

AFB I

Nennen Sie zu jeder Aussage über das Entwickeln von Mealy-Automaten, ob sie stimmt.

6 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.

Aussage 1 von 6

Die Aussage zum Testen ist die folgenreichste: Ein Entwurf kann für viele Eingaben stimmen und trotzdem einen falschen Pfeil enthalten. Gute Tests benutzen jeden Pfeil mindestens einmal — Grenzfälle eingeschlossen.

Ansatz: Denken Sie an die Reihenfolge „Ausgabe klären → Merken → Zustände“.

Weiter: Ein Automat muss vollständig sein; „nichts ausgeben“ wird mit ε notiert.

A3

Was muss er sich merken?

AFB I

Beim Entwurf ist die entscheidende Frage: Was muss sich der Automat von der bisherigen Eingabe merken? Ordnen Sie jedem Auftrag die Information zu, die seine beiden Zustände unterscheidet.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

Typische Verwechslung: Morse-Taster und Tür-Code. Bei beiden zählt nur das letzte Zeichen — aber beim Morse-Taster ist es „lang“, beim Tür-Code die 4. Merken muss sich der Automat immer nur das, was die nächste Ausgabe beeinflussen kann, nicht die ganze Vorgeschichte.

Ansatz: Fragen Sie bei jedem Auftrag: Wovon hängt die nächste Ausgabe ab?

Weiter: Bei der Großschreibung entscheidet der Zustand, ob der nächste Buchstabe groß wird — also ob seit dem Punkt schon einer kam.

A4

Probelauf: Tür mit Code 4-7

AFB I

Eine Tür soll sich öffnen, sobald direkt hintereinander die Tasten 4 und 7 gedrückt werden. Σ = {4, 7, x} (x steht für jede andere Taste), Ω = {auf}. Der Entwurf (Feld = Folgezustand / Ausgabe; z1 bedeutet „zuletzt 4“):

Übergangstabelle Türcode
Zustand	4	7	x
z0	z1 / ε	z0 / ε	z0 / ε
z1	z1 / ε	z0 / auf	z0 / ε

Wenden Sie den Entwurf auf die Eingabe 4 4 7 x 7 an und füllen Sie das Ablaufprotokoll aus. „↑“ heißt: Zustand = Folgezustand der Zeile darüber.

Füllen Sie alle Felder aus und prüfen Sie dann (Enter prüft ebenfalls). Leere Ausgabe als ε oder -.

Schritt	Zustand	Eingabe
1	z0	4
2	↑	4
3	↑	7
4	↑	x
5	↑	7
Ausgabewort

Die Folge lautet z0 → z1 → z1 → z0 → z0 → z0, das Ausgabewort ist „auf“. Entscheidend ist Schritt 2: Eine zweite 4 lässt den Automaten in z1 — sonst würde 4 4 7 die Tür nicht öffnen. Typischer Fehler in Schritt 5: noch einmal „auf“ eintragen, weil eine 7 kommt. Nach x ist die 4 aber „vergessen“.

Ansatz: Suchen Sie in jeder Zeile das Tabellenfeld „Zeile = Zustand, Spalte = Eingabe“.

Weiter: Nur das Feld (z1, 7) gibt etwas aus. Wie oft kommt der Automat mit einer 7 in z1 an?

A5

Entwurf: Großschreibung

AFB II

Ein Mealy-Automat soll Text so ausgeben, dass der erste Buchstabe des Texts und jeder erste Buchstabe nach einem Punkt groß erscheint; alle anderen Zeichen bleiben, wie sie sind. Eingaben: b = Buchstabe, p = Punkt, l = Leerzeichen. Ausgaben: groß bzw. klein (der gelesene Buchstabe als Groß- oder Kleinbuchstabe), Punkt, Leer. Aus „so. es geht“ wird „So. Es geht“. Zustände: z0 = „nächster Buchstabe wird groß“ (Start), z1 = „mitten im Satz“.

Ergänzen Sie die Übergangstabelle (Feld = Folgezustand / Ausgabe).

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

Zustand	b	p	l
z0
z1

Die Falle steckt im Feld (z0, l): Nach „so.“ folgt erst ein Leerzeichen — der Automat muss dabei in z0 bleiben, sonst wird „es“ nicht großgeschrieben. Außerdem darf kein Zeichen verloren gehen: Punkt und Leerzeichen werden ausgegeben, nicht mit ε verschluckt.

Ansatz: Gehen Sie das Beispiel „so. es geht“ Zeichen für Zeichen durch und notieren Sie, in welchem Zustand der Automat sein muss.

Weiter: Ein Leerzeichen ändert nichts daran, ob der nächste Buchstabe groß werden muss.

A6

Wie viele Pfeile?

AFB II

Ein Pfandautomat nimmt Flaschen F und Dosen D an (Σ = {F, D}). Jede Rückgabe quittiert er mit „ok“; nach jeder dritten Flasche gibt er zusätzlich „Bonus“ aus (Ausgabewort „ok Bonus“). Dosen zählen für den Bonus nicht. Bestimmen Sie, wie viele Pfeile (Schleifen mitgezählt) ein vollständiger Entwurf mit möglichst wenigen Zuständen hat.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.

Der Automat muss sich nur merken, wie viele Flaschen seit dem letzten Bonus kamen: 0, 1 oder 2 — also drei Zustände. Die dritte Flasche führt mit „F / ok Bonus“ zurück in den Zustand 0. Mit Σ = {F, D} braucht jeder Zustand zwei Pfeile: 3 · 2 = 6. Typischer Fehler: einen vierten Zustand „3 Flaschen“ einplanen (8 Pfeile). Der Bonus wird aber schon beim Übergang ausgegeben, der Zustand danach entspricht wieder 0.

Ansatz: Welche Information braucht der Automat, um beim nächsten F richtig zu entscheiden?

Weiter: Vollständig heißt: |Z| · |Σ| Pfeile. Die D-Pfeile sind Schleifen mit „D / ok“.

A7

Blocklängen mitzählen

AFB II Mix

In Kapitel 7 haben Sie die Lauflängenkodierung kennengelernt: Die Bildzeile 0001111100 wird als Folge der Blocklängen gespeichert. Ein Mealy-Automat über Σ = {0, 1} soll dabei helfen: Nach jedem Zeichen gibt er die Länge des aktuellen Blocks (einschließlich dieses Zeichens) aus, höchstens aber 3. Ω = {1, 2, 3}. Ermitteln Sie Schritt für Schritt die Ausgaben (Ziffern ohne Leerzeichen).

Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.

Ausgabewort zu 000
Ausgabewort zu 0001111100
Lauflängen der Zeile 0001111100 (Kap. 7, mit Kommas)
Nächste Ausgabe, wenn auf 0001111100 noch eine 0 folgt

Der Fünferblock aus Einsen erzeugt 1 2 3 3 3 — die Obergrenze 3 kommt aus dem endlichen Gedächtnis des Automaten: Er kann nicht beliebig weit zählen. Die Lauflängen 3, 5, 2 lassen sich deshalb nicht direkt ablesen. Typischer Fehler: beim Blockwechsel weiterzählen statt wieder mit 1 zu beginnen.

Ansatz: Jeder Wechsel von 0 auf 1 oder umgekehrt beginnt einen neuen Block mit Ausgabe 1.

Weiter: Nach 3 bleibt die Ausgabe bei 3, solange der Block weitergeht. Die letzte Zeile endet mit dem Block „00“.

A8

Welcher Test entlarvt den Fehler?

AFB II

Jonas hat den Türcode-Automaten aus A4 anders entworfen — nur das hervorgehobene Feld (z1, 4) weicht ab:

Fehlerhafter Entwurf Türcode
Zustand	4	7	x
z0	z1 / ε	z0 / ε	z0 / ε
z1	z0 / ε	z0 / auf	z0 / ε

Vergleichen Sie für jede Testeingabe Soll-Ausgabe (Entwurf aus A4) und Ist-Ausgabe (Jonas’ Entwurf). Markieren Sie alle Tests, die den Fehler aufdecken.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.

Bei Jonas springt eine zweite 4 zurück nach z0, eine dritte 4 aber wieder nach z1. Deshalb öffnet 4 4 4 7 auch bei ihm — der Test sieht nach „fehlerfrei“ aus. Aufgedeckt wird der Fehler nur, wenn eine gerade Anzahl von 4ern direkt vor der 7 steht. Bei 4 4 7 4 7 öffnet sein Automat nur einmal statt zweimal.

Ansatz: Verfolgen Sie jede Testeingabe in beiden Tabellen und vergleichen Sie die Ausgabewörter.

Weiter: Zählen Sie die 4er unmittelbar vor der 7: Ist es bei Jonas danach z1 oder z0?

A9

Fehlersuche: Stoppuhr

AFB III

Eine Stoppuhr hat die Tasten S (Start/Stopp) und R (Reset); Ω = {start, stopp, null} sind Befehle an die Anzeige. Anforderung: S startet die Uhr aus „bereit“, hält sie an, wenn sie läuft, und lässt eine angehaltene Uhr weiterlaufen. R stellt nur eine angehaltene Uhr auf null zurück; bei laufender oder bereiter Uhr passiert nichts. Mia hat folgenden Entwurf abgegeben. Überprüfen Sie ihn anhand der Anforderung.

In diesem Entwurf stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.

Beide Fehler sind typisch: Beim ersten wurde eine Anforderung („R nur bei angehaltener Uhr“) übersehen. Beim zweiten stimmt der Folgezustand, aber die Ausgabe fehlt. Zeile 2 ist korrekt — „R / ε“ als Schleife ist genau das geforderte „nichts passiert“. Mias Test in Zeile 7 ist richtig, benutzt aber keinen der beiden fehlerhaften Pfeile. Deshalb hat er die Fehler nicht aufgedeckt.

Ansatz: Prüfen Sie jeden Pfeil einzeln: Stimmen Folgezustand und Ausgabe mit der Anforderung überein?

Weiter: Lesen Sie den Satz über R genau: Wann darf R überhaupt etwas bewirken?

A10

Braucht er überhaupt Zustände?

AFB III Trick

Manche Aufträge lassen sich mit einem Mealy-Automaten mit nur einem Zustand lösen — alle Pfeile sind dann Schleifen. Beurteilen Sie für jeden Auftrag, ob ein Zustand genügt.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).

1ein Zustand genügt

2mehrere Zustände nötig

Ein Zustand genügt genau dann, wenn die Ausgabe nur vom aktuellen Zeichen abhängt. Die Falle ist „jede Ziffer doppelt“: Das klingt nach Gedächtnis, ist aber nur das Ausgabewort „3 / 33“ an einer Schleife. Auch die Caesar-Verschiebung braucht nur 26 Schleifen. Verzögern, jedes zweite Zeichen oder Leerzeichen zusammenfassen hängen dagegen vom vorigen Zeichen ab.

Ansatz: Fragen Sie: Kann ich die Ausgabe allein aus dem gerade gelesenen Zeichen bestimmen?

Weiter: Ausgabewörter aus mehreren Zeichen brauchen keinen zusätzlichen Zustand.

Übungen: Mealy-Entwurf

Übungsaufgaben