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.
Mealy-Automat: Er liest wie ein DEA Zeichen für Zeichen, gibt aber bei jedem Übergang etwas aus und übersetzt so ein Eingabewort in ein Ausgabewort.
Alphabete: Eingabealphabet \(\Sigma\) und Ausgabealphabet \(\Omega\). Ein Übergang e / a liest e, gibt a aus und wechselt den Zustand.
Ausgabe: Sie hängt vom Zustand und vom gelesenen Zeichen ab und steht am Pfeil. \(\varepsilon\) heißt: keine Ausgabe. Es gibt keine Endzustände.
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“.
Tabelle: Jedes Feld enthält Folgezustand / Ausgabe; es gibt für jeden Zustand und jedes Zeichen genau ein Feld.
Ausgabewort: die Ausgaben aller Übergänge hintereinander, \(\varepsilon\) fällt weg.
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.