Automaten mit Ausgabe
Ein Mealy-Automat liest eine Eingabe Zeichen für Zeichen wie ein DEA — gibt aber bei jedem Übergang zusätzlich etwas aus. Er übersetzt also ein Eingabewort in ein Ausgabewort.
- Eingabealphabet:\(\Sigma\) — die möglichen Eingabezeichen, z. B. \(\Sigma=\{50,\,100\}\) für Münzen in Cent.
- Ausgabealphabet:\(\Omega\) — die möglichen Ausgabezeichen, z. B. \(\Omega=\{\text{Getränk},\,50\text{ ct}\}\).
- Übergang:Pfeil mit
e / a: Eingabeelesen, Ausgabeaerzeugen, in den Folgezustand wechseln. - Ausgabewörter:statt eines Zeichens darf ein ganzes Wort ausgegeben werden, z. B.
100 / Getränk, 50 ct. - Leere Ausgabe:\(\varepsilon\) — der Übergang gibt nichts aus.
- Abhängigkeit:die Ausgabe hängt vom Zustand und vom gelesenen Zeichen ab.
- Keine Endzustände:ein Mealy-Automat nimmt nicht an oder ab — ihn interessiert nur die Ausgabe.
Ein Getränk kostet 1,50 €. Der Automat nimmt nur 50-ct-Münzen und 1-€-Münzen; seine Zustände sind das bisherige Guthaben. Ziehe eine Münze in den Schlitz (Tastatur: Tab zur Münze, Enter wirft sie ein) und beobachte Übergang und Ausgabe.
Halte fest: Dieselbe Eingabe 100 liefert je nach Zustand \(\varepsilon\), „Getränk“ oder „Getränk, 50 ct“. Die Ausgabe steht deshalb am Pfeil, nicht im Zustand.
Tabelle und Ausgabewort
Wie beim DEA lassen sich alle Übergänge in einer Tabelle angeben — jedes Feld enthält jetzt zwei Dinge: Folgezustand und Ausgabe.
- Tabellenfeld:
Folgezustand / Ausgabefür Zustand (Zeile) und Eingabezeichen (Spalte). - Vollständig:für jeden Zustand und jedes Zeichen genau ein Feld — hier \(3\cdot 2=6\).
- Ausgabewort:die Ausgaben aller Übergänge hintereinander; \(\varepsilon\) fällt dabei weg.
- Ablauf:Eingabe
50 50 100: 0 ct \(\xrightarrow{50/\varepsilon}\) 50 ct \(\xrightarrow{50/\varepsilon}\) 100 ct \(\xrightarrow{100/\text{Getränk, 50 ct}}\) 0 ct. - Ergebnis:Ausgabewort „Getränk, 50 ct“ — drei Eingabezeichen, zwei Ausgabezeichen.
Übergangstabelle des Getränkeautomaten (→ Startzustand):
| Zustand | \(50\) | \(100\) |
|---|---|---|
| 0 ct | 50 ct / \(\varepsilon\) | 100 ct / \(\varepsilon\) |
| 50 ct | 100 ct / \(\varepsilon\) | 0 ct / Getränk |
| 100 ct | 0 ct / Getränk | 0 ct / Getränk, 50 ct |
Mealy-Automat: Jeder Übergang trägt die Beschriftung e / a. Die Ausgabe \(a\in\Omega^*\) hängt vom aktuellen Zustand und vom Eingabezeichen \(e\in\Sigma\) ab; \(\varepsilon\) bedeutet „keine Ausgabe“.
Allgemeine Hinweise
ε ist nicht „0“
\(\varepsilon\) heißt: Es wird gar nichts ausgegeben. Eine Ausgabe 0 ist dagegen ein echtes Zeichen und gehört zu \(\Omega\).
Keine Endzustände
Ein Mealy-Automat zeichnet keine Doppelkreise. Er muss aber vollständig sein: An jedem Zustand braucht jedes Eingabezeichen einen Pfeil mit Ausgabe.
Schrägstrich nicht vergessen
Ein Pfeil nur mit 50 ist beim Mealy-Automaten unvollständig. Schreibe immer 50 / ε, wenn nichts ausgegeben wird.