Mealy-Automat
Ein Mealy-Automat liest nicht nur, er antwortet auch: Zu jedem Eingabezeichen gibt er ein Ausgabezeichen aus. Damit lassen sich Steuerungen und Protokolle beschreiben.
Definition
Ein Mealy-Automat ist ein endlicher Automat mit Ausgabe. Er erweitert den DEA um ein Ausgabealphabet und eine Ausgabefunktion und ist ein 7-Tupel [math]\displaystyle{ A = (Q; \Sigma; \Omega; \delta; \lambda; q_0; F) }[/math]:
- [math]\displaystyle{ Q }[/math]: endliche, nicht leere Menge der Zustände
- [math]\displaystyle{ \Sigma }[/math]: Eingabealphabet
- [math]\displaystyle{ \Omega }[/math]: Ausgabealphabet
- [math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math]: Übergangsfunktion
- [math]\displaystyle{ \lambda: Q \times \Sigma \to \Omega }[/math]: Ausgabefunktion
- [math]\displaystyle{ q_0 \in Q }[/math]: Startzustand
- [math]\displaystyle{ F \subseteq Q }[/math]: Menge der Endzustände
Was ein Tupel ist und was [math]\displaystyle{ Q \times \Sigma }[/math] bedeutet, erklärt die Definition des DEA.
Ein DEA ist ein Akzeptor: Er liefert erst am Wortende ein Ergebnis, nämlich akzeptiert oder abgelehnt. Ein Mealy-Automat ist ein Transduktor: Er übersetzt ein Eingabewort Zeichen für Zeichen in ein Ausgabewort. Dabei wird kein Eingabewort abgelehnt. Deshalb ist meist jeder Zustand Endzustand, also [math]\displaystyle{ F = Q }[/math]. In der Literatur ist auch das 6-Tupel ohne [math]\displaystyle{ F }[/math] üblich.
Darstellungsformen
Im Übergangsgraphen tragen die Kanten (Pfeile) die Beschriftung Eingabe / Ausgabe. Zuerst steht das gelesene Zeichen, dann das ausgegebene. Führen mehrere Eingabezeichen vom selben Zustand in denselben Folgezustand, stehen ihre Paare an einer gemeinsamen Kante, getrennt durch Semikolon: a / x; b / y. Zustände und Startpfeil werden wie beim DEA gezeichnet. Endzustände sind Doppelkreise. Gilt [math]\displaystyle{ F = Q }[/math], ist deshalb jeder Zustand ein Doppelkreis.
Als Tabellen werden [math]\displaystyle{ \delta }[/math] und [math]\displaystyle{ \lambda }[/math] getrennt dargestellt, je eine Tabelle. Die Zeilen sind die Zustände, die Spalten die Eingabezeichen. Die Zelle der ersten Tabelle enthält den Folgezustand [math]\displaystyle{ \delta(q; a) }[/math], die Zelle der zweiten das Ausgabezeichen [math]\displaystyle{ \lambda(q; a) }[/math]. Der Pfeil [math]\displaystyle{ \rightarrow }[/math] markiert den Startzustand, der hochgestellte Stern [math]\displaystyle{ {}^* }[/math] die Endzustände.
Arbeitsweise
Der Automat startet in [math]\displaystyle{ q_0 }[/math]. Für jedes Zeichen [math]\displaystyle{ a }[/math] im Zustand [math]\displaystyle{ q }[/math] gibt er zuerst die Ausgabe [math]\displaystyle{ \lambda(q; a) }[/math] aus und wechselt dann in den Zustand [math]\displaystyle{ \delta(q; a) }[/math].
Das Ausgabewort ist so lang wie das Eingabewort: Jedes Eingabezeichen erzeugt genau ein Ausgabezeichen. Die Ausgabe hängt vom Zustand und vom Eingabezeichen ab. Dasselbe Zeichen kann deshalb in verschiedenen Zuständen verschiedene Ausgaben erzeugen.
Ein Lauf lässt sich als Zustandsfolge mit beschrifteten Pfeilen schreiben. Über jedem Pfeil stehen wie im Übergangsgraphen das gelesene und das ausgegebene Zeichen.
Mealy-Automaten entwerfen
Ein Mealy-Automat zu einer Beschreibung in Worten entsteht in vier Schritten:
- Eingaben und Ausgaben festlegen: Jedes Ereignis, auf das der Automat reagiert, wird ein Zeichen von [math]\displaystyle{ \Sigma }[/math]. Jede mögliche Reaktion wird ein Zeichen von [math]\displaystyle{ \Omega }[/math].
- Gedächtnis festlegen: Was muss sich der Automat merken, um auf das nächste Zeichen richtig zu reagieren? Jede mögliche Antwort wird ein Zustand. Der Startzustand steht für die Lage vor dem ersten Zeichen.
- Tabellen füllen: Für jeden Zustand und jedes Eingabezeichen werden der Folgezustand und die Ausgabe festgelegt. Beide Tabellen müssen vollständig gefüllt sein.
- Prüfen: Der Automat wird mit Eingabefolgen getestet, auch mit unerwarteten.
Weil [math]\displaystyle{ \delta }[/math] und [math]\displaystyle{ \lambda }[/math] für jedes Paar aus Zustand und Zeichen festgelegt sind, reagiert der Automat auf jede Eingabe, auch auf eine unpassende.
Kommunikationsprotokolle
Ein Kommunikationsprotokoll legt fest, welche Nachrichten zwei Geräte austauschen und wie jedes Gerät auf eine Nachricht reagiert. Jede Seite lässt sich als Mealy-Automat beschreiben: Die Eingaben sind die eintreffenden Nachrichten, die Ausgaben sind die Antworten, und die Zustände halten fest, an welcher Stelle des Ablaufs sich das Gerät befindet.
Das Modell zeigt, was ein Protokoll formal leisten muss:
- Eindeutigkeit: In jedem Zustand gehört zu jeder Nachricht genau eine Antwort und genau ein Folgezustand.
- Vollständigkeit: Auch für unerwartete oder fehlerhafte Nachrichten ist eine Reaktion festgelegt.
- Gemeinsamer Stand: Kein Gerät sieht den Zustand des anderen. Beide bleiben nur dann im Takt, wenn sie nach denselben festgelegten Regeln arbeiten.
Protokolle in Rechnernetzen wie TCP sind auf diese Weise mit Zuständen und Antworten festgelegt. Sie überwachen zusätzlich die Zeit, damit eine verlorene Nachricht den Ablauf nicht dauerhaft anhält.
Moore-Automat
Beim Moore-Automaten hängt die Ausgabe nur vom Zustand ab: [math]\displaystyle{ \lambda: Q \to \Omega }[/math]. Im Übergangsgraphen steht sie deshalb im Zustand, geschrieben als Zustand/Ausgabe, und die Kanten tragen nur das Eingabezeichen. Der Automat gibt die Ausgabe eines Zustands aus, sobald er diesen Zustand betritt. Auch der Startzustand hat eine Ausgabe, die Anfangsausgabe. Sie erscheint, bevor das erste Zeichen gelesen ist. Zählt man sie mit, entstehen bei [math]\displaystyle{ n }[/math] Eingabezeichen [math]\displaystyle{ n + 1 }[/math] Ausgabezeichen. Wie beim Mealy-Automaten ist meist jeder Zustand Endzustand ([math]\displaystyle{ F = Q }[/math]) und damit ein Doppelkreis.
Beide Modelle lassen sich ineinander umwandeln:
- Vom Mealy- zum Moore-Automaten: Jeder Zustand wird für jede Ausgabe, mit der eine Kante in ihn führt, einmal angelegt. Führen in einen Zustand Kanten mit verschiedenen Ausgaben, entstehen aus ihm also mehrere Zustände. Der Moore-Automat braucht deshalb oft mehr Zustände. Jede Kante führt in den Zustand, der ihre Ausgabe trägt. Für den Startzustand muss zusätzlich eine Anfangsausgabe festgelegt werden, denn der Mealy-Automat gibt vor dem ersten Zeichen nichts aus. Startzustand des Moore-Automaten ist der Startzustand des Mealy-Automaten mit dieser Anfangsausgabe. Führt keine Kante mit dieser Ausgabe in den Startzustand, kommt er als weiterer Zustand hinzu. Auf die Anfangsausgabe folgt dann genau das Ausgabewort des Mealy-Automaten.
- Vom Moore- zum Mealy-Automaten: Die Ausgabe eines Zustands wandert auf alle Kanten, die in diesen Zustand führen. Die Anfangsausgabe entfällt.
Welches Modell besser passt, hängt von der Anwendung ab. Der Mealy-Automat passt, wenn auf jedes einzelne Ereignis eine Reaktion folgen soll. Er kommt oft mit weniger Zuständen aus. Der Moore-Automat passt, wenn eine Ausgabe so lange gelten soll, wie der Automat in einem Zustand bleibt, etwa das Licht einer Ampel.
Umsetzung in Java
Der aktuelle Zustand wird als Attribut vom Typ int gespeichert. Die Funktionen [math]\displaystyle{ \delta }[/math] und [math]\displaystyle{ \lambda }[/math] liegen als zweidimensionale Arrays vor: Die Zeile ist der Zustand, die Spalte das Eingabezeichen.
Eine Methode verarbeitet ein einzelnes Zeichen. Sie liest zuerst die Ausgabe aus dem Array für [math]\displaystyle{ \lambda }[/math] und wechselt dann mit dem Array für [math]\displaystyle{ \delta }[/math] den Zustand. Eine zweite Methode ruft die erste in einer Schleife für jedes Zeichen des Eingabewortes auf und hängt die Ausgaben aneinander. Jedes neue Objekt beginnt im Startzustand. Das vollständige Programm steht im Beispiel Bonbonautomat in Java umsetzen.
Beispiele
Bonbonautomat als Mealy-Automaten angeben

Ein Bonbonautomat hat zwei Eingaben: [math]\displaystyle{ M }[/math] für Münze einwerfen und [math]\displaystyle{ H }[/math] für Hebel drehen. Er hat zwei Ausgaben: [math]\displaystyle{ B }[/math] für Bonbon und [math]\displaystyle{ N }[/math] für nichts. Zwei Zustände genügen: [math]\displaystyle{ q_0 }[/math] bedeutet, dass keine Münze eingeworfen ist, [math]\displaystyle{ q_1 }[/math] bedeutet, dass eine Münze eingeworfen ist.
- [math]\displaystyle{ Q = \{q_0; q_1\} }[/math]
- [math]\displaystyle{ \Sigma = \{M; H\} }[/math]
- [math]\displaystyle{ \Omega = \{B; N\} }[/math]
- Startzustand [math]\displaystyle{ q_0 }[/math]
- [math]\displaystyle{ F = Q }[/math], im Bild sind deshalb beide Zustände Doppelkreise
Die Übergangsfunktion [math]\displaystyle{ \delta }[/math] und die Ausgabefunktion [math]\displaystyle{ \lambda }[/math] stehen in zwei Tabellen:
| [math]\displaystyle{ \delta }[/math] | [math]\displaystyle{ M }[/math] | [math]\displaystyle{ H }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*q_0 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ {}^*q_1 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ \lambda }[/math] | [math]\displaystyle{ M }[/math] | [math]\displaystyle{ H }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*q_0 }[/math] | [math]\displaystyle{ N }[/math] | [math]\displaystyle{ N }[/math] |
| [math]\displaystyle{ {}^*q_1 }[/math] | [math]\displaystyle{ N }[/math] | [math]\displaystyle{ B }[/math] |
Beispiel für das Lesen der Tabellen: Im Zustand [math]\displaystyle{ q_1 }[/math] führt [math]\displaystyle{ H }[/math] zu [math]\displaystyle{ \delta(q_1; H) = q_0 }[/math] mit der Ausgabe [math]\displaystyle{ \lambda(q_1; H) = B }[/math]. Nur in dieser Lage gibt der Automat ein Bonbon aus: erst die Münze, dann der Hebel.
Ausgabewort bestimmen
Gesucht ist die Ausgabe des Bonbonautomaten für die Eingabe [math]\displaystyle{ HMMH }[/math]. Der Lauf beginnt in [math]\displaystyle{ q_0 }[/math].
- [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ H }[/math]: Die Kante
H / Ngibt [math]\displaystyle{ N }[/math] aus, der Automat bleibt in [math]\displaystyle{ q_0 }[/math]. - [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ M }[/math]: Die Kante
M / Ngibt [math]\displaystyle{ N }[/math] aus, der Automat wechselt nach [math]\displaystyle{ q_1 }[/math]. - [math]\displaystyle{ q_1 }[/math] liest [math]\displaystyle{ M }[/math]: Die Kante
M / Ngibt [math]\displaystyle{ N }[/math] aus, der Automat bleibt in [math]\displaystyle{ q_1 }[/math]. - [math]\displaystyle{ q_1 }[/math] liest [math]\displaystyle{ H }[/math]: Die Kante
H / Bgibt [math]\displaystyle{ B }[/math] aus, der Automat wechselt nach [math]\displaystyle{ q_0 }[/math].
Als Lauf geschrieben, über jedem Pfeil stehen Eingabe und Ausgabe:
- [math]\displaystyle{ q_0 \xrightarrow{H / N} q_0 \xrightarrow{M / N} q_1 \xrightarrow{M / N} q_1 \xrightarrow{H / B} q_0 }[/math]
Die Ausgaben in dieser Reihenfolge ergeben das Ausgabewort [math]\displaystyle{ NNNB }[/math]. Es ist so lang wie die Eingabe. Das Bonbon erscheint beim letzten Zeichen: Der erste Hebel ohne Münze bewirkt nichts, die zweite Münze ändert nichts, erst der letzte Hebel gibt ein Bonbon aus.
Empfänger eines Protokolls als Mealy-Automaten entwerfen

Ein Sender schickt Datenpakete an einen Empfänger. Der Empfänger bestätigt jedes Paket mit einer kurzen Antwort, der Quittung. Geht eine Quittung verloren, schickt der Sender dasselbe Paket noch einmal. Damit der Empfänger ein wiederholtes Paket nicht doppelt verarbeitet, tragen die Pakete abwechselnd die Nummern 0 und 1. Der Empfänger beantwortet jedes Paket sofort: mit [math]\displaystyle{ A }[/math] (angenommen), wenn er es als neues Paket annimmt, oder mit [math]\displaystyle{ D }[/math] (Duplikat), wenn er es als Wiederholung verwirft.
Schritt 1: Eingaben und Ausgaben festlegen. Die Eingaben sind die Paketnummern, die Ausgaben die Quittungen: [math]\displaystyle{ \Sigma = \{0; 1\} }[/math] und [math]\displaystyle{ \Omega = \{A; D\} }[/math].
Schritt 2: Gedächtnis festlegen. Der Empfänger muss sich nur merken, welche Nummer das nächste neue Paket trägt. Zwei Zustände genügen: In [math]\displaystyle{ q_0 }[/math] erwartet er die Nummer 0, in [math]\displaystyle{ q_1 }[/math] die Nummer 1. Das erste Paket trägt die Nummer 0, deshalb ist [math]\displaystyle{ q_0 }[/math] der Startzustand.
Schritt 3: Tabellen füllen. Trifft die erwartete Nummer ein, antwortet der Empfänger mit [math]\displaystyle{ A }[/math] und erwartet danach die andere Nummer. Trifft die andere Nummer ein, ist das Paket eine Wiederholung: Er antwortet mit [math]\displaystyle{ D }[/math] und bleibt im selben Zustand.
| [math]\displaystyle{ \delta }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 1 }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*q_0 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ {}^*q_1 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ \lambda }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 1 }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*q_0 }[/math] | [math]\displaystyle{ A }[/math] | [math]\displaystyle{ D }[/math] |
| [math]\displaystyle{ {}^*q_1 }[/math] | [math]\displaystyle{ D }[/math] | [math]\displaystyle{ A }[/math] |
Schritt 4: Prüfen. Der Sender schickt die Pakete 0 und 1, wiederholt das Paket 1 und schickt dann das nächste Paket 0. Für die Eingabe [math]\displaystyle{ 0110 }[/math] durchläuft der Automat:
- [math]\displaystyle{ q_0 \xrightarrow{0 / A} q_1 \xrightarrow{1 / A} q_0 \xrightarrow{1 / D} q_0 \xrightarrow{0 / A} q_1 }[/math]
Die Ausgabe ist [math]\displaystyle{ AADA }[/math]: Das wiederholte Paket wird als Duplikat erkannt, alle anderen werden angenommen.
Der Automat erfüllt die Anforderungen an ein Kommunikationsprotokoll: In jedem Zustand ist für jede Paketnummer genau eine Antwort festgelegt, auch für die unerwartete.
Bonbonautomat als Moore-Automaten darstellen

Beim Moore-Automaten steht die Ausgabe im Zustand. Die Zustände heißen [math]\displaystyle{ q_0/N }[/math], [math]\displaystyle{ q_1/N }[/math] und [math]\displaystyle{ q_2/B }[/math]: Der Name nennt den Zustand und seine Ausgabe.
- [math]\displaystyle{ q_0/N }[/math]: keine Münze eingeworfen, Ausgabe [math]\displaystyle{ N }[/math]
- [math]\displaystyle{ q_1/N }[/math]: Münze eingeworfen, Ausgabe [math]\displaystyle{ N }[/math]
- [math]\displaystyle{ q_2/B }[/math]: Bonbon wird ausgegeben, Ausgabe [math]\displaystyle{ B }[/math]
Der Moore-Automat hat drei statt zwei Zustände. Der Grund: Beim Mealy-Automaten führen nach [math]\displaystyle{ q_0 }[/math] Kanten mit den Ausgaben [math]\displaystyle{ N }[/math] und [math]\displaystyle{ B }[/math]. Der Zustand „keine Münze“ wird deshalb für jede der beiden Ausgaben einmal angelegt, als [math]\displaystyle{ q_0/N }[/math] und als [math]\displaystyle{ q_2/B }[/math]. Nach [math]\displaystyle{ q_1 }[/math] führen nur Kanten mit der Ausgabe [math]\displaystyle{ N }[/math], dieser Zustand wird einmal angelegt. Startzustand ist [math]\displaystyle{ q_0/N }[/math]: Als Anfangsausgabe wird [math]\displaystyle{ N }[/math] festgelegt, denn vor dem ersten Zeichen gibt es kein Bonbon. Den Zustand [math]\displaystyle{ q_0/N }[/math] gibt es schon, ein weiterer Zustand ist nicht nötig.
Der Hebel nach der Münze führt von [math]\displaystyle{ q_1/N }[/math] nach [math]\displaystyle{ q_2/B }[/math] und gibt dort [math]\displaystyle{ B }[/math] aus. Beim Mealy-Automaten genügt dafür die Kante H / B. Von [math]\displaystyle{ q_2/B }[/math] führt [math]\displaystyle{ M }[/math] nach [math]\displaystyle{ q_1/N }[/math] und [math]\displaystyle{ H }[/math] nach [math]\displaystyle{ q_0/N }[/math], genau wie von [math]\displaystyle{ q_0/N }[/math]. Alle drei Zustände sind Endzustände und deshalb Doppelkreise.
Für die Eingabe [math]\displaystyle{ HMMH }[/math] durchläuft der Moore-Automat diese Zustände:
- [math]\displaystyle{ q_0/N \xrightarrow{H} q_0/N \xrightarrow{M} q_1/N \xrightarrow{M} q_1/N \xrightarrow{H} q_2/B }[/math]
Jeder Zustand gibt seine Ausgabe aus, auch der Startzustand. Das Ausgabewort ist [math]\displaystyle{ NNNNB }[/math]: fünf Zeichen für vier Eingabezeichen. Ohne die Anfangsausgabe bleibt [math]\displaystyle{ NNNB }[/math], das Ausgabewort des Mealy-Automaten.
Mealy-Automaten in einen Moore-Automaten umwandeln
Der Empfänger aus dem Beispiel Empfänger eines Protokolls als Mealy-Automaten entwerfen wird in einen Moore-Automaten umgewandelt.
Schritt 1: Zustände anlegen. Nach [math]\displaystyle{ q_0 }[/math] führen die Kanten 1 / D (von [math]\displaystyle{ q_0 }[/math]) und 1 / A (von [math]\displaystyle{ q_1 }[/math]). Der Zustand wird deshalb zweimal angelegt: als [math]\displaystyle{ q_0/A }[/math] und als [math]\displaystyle{ q_0/D }[/math]. Nach [math]\displaystyle{ q_1 }[/math] führen die Kanten 0 / A (von [math]\displaystyle{ q_0 }[/math]) und 0 / D (von [math]\displaystyle{ q_1 }[/math]). Es entstehen [math]\displaystyle{ q_1/A }[/math] und [math]\displaystyle{ q_1/D }[/math]. Die neuen Zustände behalten hier den Namen des Mealy-Zustands und unterscheiden sich durch die Ausgabe hinter dem Schrägstrich. Im vorigen Beispiel hat der zweite Zustand für „keine Münze“ stattdessen eine neue Nummer erhalten ([math]\displaystyle{ q_2/B }[/math]). Beide Benennungen sind möglich.
Schritt 2: Startzustand festlegen. Vor dem ersten Paket gibt es nichts zu quittieren. Als Anfangsausgabe wird deshalb ein neues Ausgabezeichen [math]\displaystyle{ N }[/math] (noch keine Quittung) festgelegt. Keine Kante führt mit der Ausgabe [math]\displaystyle{ N }[/math] nach [math]\displaystyle{ q_0 }[/math]. Der Startzustand [math]\displaystyle{ q_0/N }[/math] kommt deshalb als fünfter Zustand hinzu.
Schritt 3: Kanten übertragen. Jede Kante führt in den Zustand, der ihre Ausgabe trägt. Die drei Zustände, die aus [math]\displaystyle{ q_0 }[/math] entstanden sind, haben dieselben Kanten: [math]\displaystyle{ 0 }[/math] führt nach [math]\displaystyle{ q_1/A }[/math], [math]\displaystyle{ 1 }[/math] nach [math]\displaystyle{ q_0/D }[/math]. Von den beiden Zuständen, die aus [math]\displaystyle{ q_1 }[/math] entstanden sind, führt [math]\displaystyle{ 0 }[/math] nach [math]\displaystyle{ q_1/D }[/math] und [math]\displaystyle{ 1 }[/math] nach [math]\displaystyle{ q_0/A }[/math].
| [math]\displaystyle{ \delta }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 1 }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*q_0/N }[/math] | [math]\displaystyle{ q_1/A }[/math] | [math]\displaystyle{ q_0/D }[/math] |
| [math]\displaystyle{ {}^*q_0/A }[/math] | [math]\displaystyle{ q_1/A }[/math] | [math]\displaystyle{ q_0/D }[/math] |
| [math]\displaystyle{ {}^*q_0/D }[/math] | [math]\displaystyle{ q_1/A }[/math] | [math]\displaystyle{ q_0/D }[/math] |
| [math]\displaystyle{ {}^*q_1/A }[/math] | [math]\displaystyle{ q_1/D }[/math] | [math]\displaystyle{ q_0/A }[/math] |
| [math]\displaystyle{ {}^*q_1/D }[/math] | [math]\displaystyle{ q_1/D }[/math] | [math]\displaystyle{ q_0/A }[/math] |
Der Moore-Automat hat fünf Zustände, der Mealy-Automat zwei. In den Startzustand [math]\displaystyle{ q_0/N }[/math] führt keine Kante: Der Automat durchläuft ihn nur am Anfang.
Schritt 4: Prüfen. Für die Eingabe [math]\displaystyle{ 0110 }[/math] durchläuft der Moore-Automat diese Zustände:
- [math]\displaystyle{ q_0/N \xrightarrow{0} q_1/A \xrightarrow{1} q_0/A \xrightarrow{1} q_0/D \xrightarrow{0} q_1/A }[/math]
Das Ausgabewort ist [math]\displaystyle{ NAADA }[/math]: die Anfangsausgabe [math]\displaystyle{ N }[/math], danach das Ausgabewort [math]\displaystyle{ AADA }[/math] des Mealy-Automaten.
Bonbonautomat in Java umsetzen
Das Programm setzt den Bonbonautomaten nach dem Abschnitt Umsetzung in Java um. Die Zustände [math]\displaystyle{ q_0 }[/math] und [math]\displaystyle{ q_1 }[/math] haben die Nummern 0 und 1, die Eingaben [math]\displaystyle{ M }[/math] und [math]\displaystyle{ H }[/math] die Spalten 0 und 1.
public class Bonbonautomat {
// Zeilen: Zustände q0, q1; Spalten: Eingaben M, H
private static final int[][] DELTA = {{1, 0}, {1, 0}};
private static final char[][] LAMBDA = {{'N', 'N'}, {'N', 'B'}};
private int zustand = 0;
public char lies(char eingabe) {
int spalte = eingabe == 'M' ? 0 : 1;
char ausgabe = LAMBDA[zustand][spalte];
zustand = DELTA[zustand][spalte];
return ausgabe;
}
public String verarbeite(String eingaben) {
StringBuilder ausgaben = new StringBuilder();
for (char eingabe : eingaben.toCharArray()) {
ausgaben.append(lies(eingabe));
}
return ausgaben.toString();
}
public static void main(String[] args) {
System.out.println(new Bonbonautomat().verarbeite("HMMH"));
System.out.println(new Bonbonautomat().verarbeite("MH"));
}
}
Die Methode lies verarbeitet ein Zeichen, die Methode verarbeite ein ganzes Eingabewort. Das Programm gibt für [math]\displaystyle{ HMMH }[/math] das Ausgabewort [math]\displaystyle{ NNNB }[/math] aus und für [math]\displaystyle{ MH }[/math] das Ausgabewort [math]\displaystyle{ NB }[/math]. Für jede Eingabefolge wird ein neues Objekt erzeugt, damit der Automat wieder in [math]\displaystyle{ q_0 }[/math] beginnt.
Das Programm setzt voraus, dass die Eingabe nur die Zeichen [math]\displaystyle{ M }[/math] und [math]\displaystyle{ H }[/math] enthält: Die Methode lies behandelt jedes Zeichen, das nicht M ist, wie H. Soll das Programm fremde Zeichen erkennen, muss es sie vor der Verarbeitung prüfen und zum Beispiel mit einer Fehlermeldung abweisen.