Vom Auftrag zum Automaten
Beim Entwurf eines Mealy-Automaten fragst du zuerst, was er ausgeben soll — und dann, was er sich dafür von der bisherigen Eingabe merken muss.
- Alphabete:\(\Sigma\) und \(\Omega\) festlegen, z. B. \(\Sigma=\Omega=\{0,\,1\}\).
- Ausgabe klären:wann soll was ausgegeben werden? Mit Beispielpaaren (Eingabewort → Ausgabewort) festhalten.
- Merken:welche Information über die Vergangenheit braucht die Ausgabe? Jede nötige Information wird ein Zustand mit Bedeutung.
- Start:der Zustand, der zur Lage vor dem ersten Zeichen passt.
- Übergänge:für jeden Zustand und jedes Zeichen Folgezustand und Ausgabe festlegen:
e / a. - Ausgabewörter:darf mehr als ein Zeichen erscheinen, steht das ganze Wort am Pfeil, z. B.
1 / an. - Testen:Testeingaben durchlaufen und die Ist-Ausgabe Zeichen für Zeichen mit der Soll-Ausgabe vergleichen.
Aufgabe: Ein Automat liest ein Signal aus Nullen und Einsen und gibt 1 genau dann aus, wenn sich das Zeichen gegenüber dem vorigen ändert — sonst 0 (vor dem Start gilt „zuletzt 0“). Alle drei Entwürfe merken sich in z0 bzw. z1 das zuletzt gelesene Zeichen. Wähle einen Entwurf und vergleiche seine Ist-Ausgabe mit der Soll-Ausgabe. Ein Klick auf ein Eingabe-Bit schaltet es um.
Halte fest: Ein Entwurf ist erst korrekt, wenn Ist- und Soll-Ausgabe für jede Testeingabe Zeichen für Zeichen übereinstimmen. Schon eine falsche Ausgabe an einem einzigen Pfeil verrät sich — aber nur bei Testeingaben, die diesen Pfeil auch benutzen.
Testen mit dem Ablaufprotokoll
Ein Ablaufprotokoll hält jeden Schritt als Zeile fest. So siehst du genau, welcher Übergang welche Ausgabe erzeugt — und wo ein Entwurf von der Soll-Ausgabe abweicht.
- Zeile:Schritt, aktueller Zustand, gelesenes Zeichen, Ausgabe, Folgezustand.
- Verkettung:der Folgezustand einer Zeile ist der Zustand der nächsten Zeile.
- Ausgabewort:die Ausgabe-Spalte von oben nach unten gelesen (\(\varepsilon\) fällt weg).
- Vergleich:Ausgabewort neben die Soll-Ausgabe schreiben — jede Abweichung zeigt auf einen falschen Pfeil.
Ablaufprotokoll des korrekten Flankenerkenners für das Eingabewort 1001:
| Schritt | Zustand | Eingabe | Ausgabe | Folgezustand |
|---|---|---|---|---|
| 1 | z0 | 1 | 1 | z1 |
| 2 | z1 | 0 | 1 | z0 |
| 3 | z0 | 0 | 0 | z0 |
| 4 | z0 | 1 | 1 | z1 |
Ausgabewort 1101 — genau die Soll-Ausgabe: Änderung, Änderung, keine, Änderung.
Entwurf: Zustände speichern, was sich der Automat von der Vergangenheit merken muss; die Ausgabe steht am Übergang e / a und darf vom aktuellen Zeichen abhängen. Korrekt ist ein Entwurf, wenn er für jede Eingabe das geforderte Ausgabewort liefert.
Allgemeine Hinweise
Ausgabe gehört an den Pfeil
Gibt jeder Pfeil aus einem Zustand dasselbe aus, ignoriert der Automat das aktuelle Zeichen — die Ausgabe hinkt dann einen Takt hinterher (Entwurf A).
Grenzfälle testen
Teste ein Wort, das mit 1 beginnt, lange Blöcke gleicher Zeichen und ständigen Wechsel wie 0101. So wird jeder Pfeil mindestens einmal benutzt.
Schleifen genau prüfen
Schleifen werden bei langen gleichen Blöcken oft durchlaufen. Eine falsche Ausgabe an einer Schleife erzeugt deshalb gleich mehrere Fehler (Entwurf C).