Mealy-Automat: Unterschied zwischen den Versionen

Die Seite wurde neu angelegt: „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 erweitert den DEA um ein Ausgabealphabet und eine Ausgabefunktion. Er ist ein 7-Tupel <math>A = (Q, \Sigma, \Omega, \delta, \lambda, q0, F)</math>: * <math>Q</math>: endliche, nicht leere Menge der Zustände * <math>\…“
 
Keine Bearbeitungszusammenfassung
 
Zeile 2: Zeile 2:


==Definition==
==Definition==
Ein Mealy-Automat erweitert den [[Deterministischer endlicher Automat|DEA]] um ein Ausgabealphabet und eine Ausgabefunktion. Er ist ein 7-Tupel <math>A = (Q, \Sigma, \Omega, \delta, \lambda, q0, F)</math>:
Ein '''Mealy-Automat''' ist ein [[Endlicher Automat|endlicher Automat]] mit Ausgabe. Er erweitert den [[Deterministischer endlicher Automat|DEA]] um ein Ausgabealphabet und eine Ausgabefunktion und ist ein 7-Tupel <math>A = (Q; \Sigma; \Omega; \delta; \lambda; q_0; F)</math>:
* <math>Q</math>: endliche, nicht leere Menge der Zustände
* <math>Q</math>: endliche, nicht leere Menge der Zustände
* <math>\Sigma</math>: Eingabealphabet
* <math>\Sigma</math>: Eingabealphabet
Zeile 8: Zeile 8:
* <math>\delta: Q \times \Sigma \to Q</math>: Übergangsfunktion
* <math>\delta: Q \times \Sigma \to Q</math>: Übergangsfunktion
* <math>\lambda: Q \times \Sigma \to \Omega</math>: Ausgabefunktion
* <math>\lambda: Q \times \Sigma \to \Omega</math>: Ausgabefunktion
* <math>q0 \in Q</math>: Startzustand
* <math>q_0 \in Q</math>: Startzustand
* <math>F \subseteq Q</math>: Menge der Endzustände
* <math>F \subseteq Q</math>: Menge der Endzustände


Oft ist jeder Zustand Endzustand, also <math>F = Q</math>. In der Literatur ist auch das 6-Tupel ohne <math>F</math> üblich.
Was ein Tupel ist und was <math>Q \times \Sigma</math> bedeutet, erklärt die [[Deterministischer endlicher Automat#Definition|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>F = Q</math>. In der Literatur ist auch das 6-Tupel ohne <math>F</math> üblich.


==Darstellungsformen==
==Darstellungsformen==
Im Übergangsgraphen tragen die Kanten die Beschriftung <code>Eingabe / Ausgabe</code>. Zuerst steht das gelesene Zeichen, dann das ausgegebene. Zustände und Startpfeil werden wie beim [[Deterministischer endlicher Automat#Darstellungsformen|DEA]] gezeichnet. Gilt <math>F = Q</math>, entfällt der Doppelkreis.
Im Übergangsgraphen tragen die Kanten (Pfeile) die Beschriftung <code>Eingabe / Ausgabe</code>. 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: <code>a / x; b / y</code>. Zustände und Startpfeil werden wie beim [[Deterministischer endlicher Automat#Darstellungsformen|DEA]] gezeichnet. Endzustände sind Doppelkreise. Gilt <math>F = Q</math>, ist deshalb jeder Zustand ein Doppelkreis.


Als Tabellen werden <math>\delta</math> und <math>\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>\delta(q, a)</math>, die Zelle der zweiten das Ausgabezeichen <math>\lambda(q, a)</math>.
Als Tabellen werden <math>\delta</math> und <math>\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>\delta(q; a)</math>, die Zelle der zweiten das Ausgabezeichen <math>\lambda(q; a)</math>. Der Pfeil <math>\rightarrow</math> markiert den Startzustand, der hochgestellte Stern <math>{}^*</math> die Endzustände.


==Arbeitsweise==
==Arbeitsweise==
Der Automat startet in q0. Für jedes Zeichen <math>a</math> im Zustand <math>q</math> gibt er zuerst die Ausgabe <math>\lambda(q, a)</math> aus und wechselt dann in den Zustand <math>\delta(q, a)</math>.
Der Automat startet in <math>q_0</math>. Für jedes Zeichen <math>a</math> im Zustand <math>q</math> gibt er zuerst die Ausgabe <math>\lambda(q; a)</math> aus und wechselt dann in den Zustand <math>\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.
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.


==Moore-Automat==
Ein Lauf lässt sich als Zustandsfolge mit beschrifteten Pfeilen schreiben. Über jedem Pfeil stehen wie im Übergangsgraphen das gelesene und das ausgegebene Zeichen.
Beim Moore-Automaten hängt die Ausgabe nur vom Zustand ab: <math>\lambda: Q \to \Omega</math>. Die Ausgabe gehört zum erreichten Zustand und erscheint dadurch einen Schritt später als beim Mealy-Automaten.
 
==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>\Sigma</math>. Jede mögliche Reaktion wird ein Zeichen von <math>\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>\delta</math> und <math>\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.


Beide Modelle lassen sich ineinander umwandeln. Der Moore-Automat braucht oft mehr Zustände, weil jeder Zustand nur eine Ausgabe liefern kann.
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.


==Umsetzung in Java==
==Moore-Automat==
Der Zustand wird als <code>int</code> gespeichert. Die Funktionen <math>\delta</math> und <math>\lambda</math> liegen als [[Array|zweidimensionale Arrays]] vor: Die Zeile ist der Zustand, die Spalte das Eingabezeichen. Eine Schleife liest das Eingabewort Zeichen für Zeichen. Sie hängt zuerst die Ausgabe an und wechselt dann den Zustand.
Beim Moore-Automaten hängt die Ausgabe nur vom Zustand ab: <math>\lambda: Q \to \Omega</math>. Im Übergangsgraphen steht sie deshalb im Zustand, geschrieben als <code>Zustand/Ausgabe</code>, 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>n</math> Eingabezeichen <math>n + 1</math> Ausgabezeichen. Wie beim Mealy-Automaten ist meist jeder Zustand Endzustand (<math>F = Q</math>) und damit ein Doppelkreis.


<syntaxhighlight lang="java">
Beide Modelle lassen sich ineinander umwandeln:
public class Bonbonautomat {
* '''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.
    // Zeilen: Zustaende q0, q1; Spalten: Eingaben M, H
* '''Vom Moore- zum Mealy-Automaten:''' Die Ausgabe eines Zustands wandert auf alle Kanten, die in diesen Zustand führen. Die Anfangsausgabe entfällt.
    private static final int[][] DELTA = {{1, 0}, {1, 0}};
    private static final char[][] LAMBDA = {{'N', 'N'}, {'N', 'B'}};


    public static String uebersetze(String eingabe) {
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.
        int zustand = 0;
        StringBuilder ausgabe = new StringBuilder();
        for (char zeichen : eingabe.toCharArray()) {
            int spalte = zeichen == 'M' ? 0 : 1;
            ausgabe.append(LAMBDA[zustand][spalte]);
            zustand = DELTA[zustand][spalte];
        }
        return ausgabe.toString();
    }


    public static void main(String[] args) {
==Umsetzung in Java==
        System.out.println(uebersetze("HMMH"));
Der aktuelle Zustand wird als Attribut vom Typ <code>int</code> gespeichert. Die Funktionen <math>\delta</math> und <math>\lambda</math> liegen als [[Array#Mehrdimensionale Arrays|zweidimensionale Arrays]] vor: Die Zeile ist der Zustand, die Spalte das Eingabezeichen.
        System.out.println(uebersetze("MH"));
    }
}
</syntaxhighlight>


Die Methode <code>uebersetze</code> liefert zu einem Eingabewort das Ausgabewort.
Eine Methode verarbeitet ein einzelnes Zeichen. Sie liest zuerst die Ausgabe aus dem Array für <math>\lambda</math> und wechselt dann mit dem Array für <math>\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|Bonbonautomat in Java umsetzen]].


==Beispiele==
==Beispiele==
===Bonbonautomat als Mealy-Automaten angeben===
===Bonbonautomat als Mealy-Automaten angeben===
[[Datei:Mealy-Automat Bonbonautomat.png|mini|Bonbonautomat als Mealy-Automat]]
[[Datei:Mealy-Automat Bonbonautomat.png|mini|Bonbonautomat als Mealy-Automat]]
Ein Bonbonautomat hat zwei Eingaben: M für Münze einwerfen und H für Hebel drehen. Er hat zwei Ausgaben: B für Bonbon und N für nichts. Zwei Zustände genügen: q0 bedeutet, dass keine Münze eingeworfen ist, q1 bedeutet, dass eine Münze eingeworfen ist.
Ein Bonbonautomat hat zwei Eingaben: <math>M</math> für Münze einwerfen und <math>H</math> für Hebel drehen. Er hat zwei Ausgaben: <math>B</math> für Bonbon und <math>N</math> für nichts. Zwei Zustände genügen: <math>q_0</math> bedeutet, dass keine Münze eingeworfen ist, <math>q_1</math> bedeutet, dass eine Münze eingeworfen ist.


* <math>Q = \{q0, q1\}</math>
* <math>Q = \{q_0; q_1\}</math>
* <math>\Sigma = \{M, H\}</math>
* <math>\Sigma = \{M; H\}</math>
* <math>\Omega = \{B, N\}</math>
* <math>\Omega = \{B; N\}</math>
* <math>F = Q</math>
* Startzustand <math>q_0</math>
* <math>F = Q</math>, im Bild sind deshalb beide Zustände Doppelkreise


Die Übergangsfunktion <math>\delta</math> und die Ausgabefunktion <math>\lambda</math> stehen in zwei Tabellen:
Die Übergangsfunktion <math>\delta</math> und die Ausgabefunktion <math>\lambda</math> stehen in zwei Tabellen:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! δ !! M !! H
|+ style="white-space:nowrap" | Übergangsfunktion <math>\delta(q; a)</math> (Folgezustand)
! <math>\delta</math> !! <math>M</math> !! <math>H</math>
|-
|-
| q0 || q1 || q0
| <math>\rightarrow {}^*q_0</math> || <math>q_1</math> || <math>q_0</math>
|-
|-
| q1 || q1 || q0
| <math>{}^*q_1</math> || <math>q_1</math> || <math>q_0</math>
|}
|}


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! λ !! M !! H
|+ style="white-space:nowrap" | Ausgabefunktion <math>\lambda(q; a)</math> (Ausgabezeichen)
! <math>\lambda</math> !! <math>M</math> !! <math>H</math>
|-
|-
| q0 || N || N
| <math>\rightarrow {}^*q_0</math> || <math>N</math> || <math>N</math>
|-
|-
| q1 || N || B
| <math>{}^*q_1</math> || <math>N</math> || <math>B</math>
|}
|}


Beispiel für das Lesen der Tabellen: Im Zustand q1 führt H zu <math>\delta(q1, H) = q0</math> mit der Ausgabe <math>\lambda(q1, H) = B</math>. Nur in dieser Lage gibt der Automat ein Bonbon aus: erst die Münze, dann der Hebel.
Beispiel für das Lesen der Tabellen: Im Zustand <math>q_1</math> führt <math>H</math> zu <math>\delta(q_1; H) = q_0</math> mit der Ausgabe <math>\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===
===Ausgabewort bestimmen===
Gesucht ist die Ausgabe des Bonbonautomaten für die Eingabe HMMH. Der Lauf beginnt in q0.
Gesucht ist die Ausgabe des Bonbonautomaten für die Eingabe <math>HMMH</math>. Der Lauf beginnt in <math>q_0</math>.
 
# <math>q_0</math> liest <math>H</math>: Die Kante <code>H / N</code> gibt <math>N</math> aus, der Automat bleibt in <math>q_0</math>.
# <math>q_0</math> liest <math>M</math>: Die Kante <code>M / N</code> gibt <math>N</math> aus, der Automat wechselt nach <math>q_1</math>.
# <math>q_1</math> liest <math>M</math>: Die Kante <code>M / N</code> gibt <math>N</math> aus, der Automat bleibt in <math>q_1</math>.
# <math>q_1</math> liest <math>H</math>: Die Kante <code>H / B</code> gibt <math>B</math> aus, der Automat wechselt nach <math>q_0</math>.
 
Als Lauf geschrieben, über jedem Pfeil stehen Eingabe und Ausgabe:
 
:<math>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>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===
[[Datei:Mealy-Automat Empfänger mit Quittung.png|mini|Empfänger mit Quittung als Mealy-Automat]]
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>A</math> (angenommen), wenn er es als neues Paket annimmt, oder mit <math>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>\Sigma = \{0; 1\}</math> und <math>\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>q_0</math> erwartet er die Nummer 0, in <math>q_1</math> die Nummer 1. Das erste Paket trägt die Nummer 0, deshalb ist <math>q_0</math> der Startzustand.
 
'''Schritt 3: Tabellen füllen.''' Trifft die erwartete Nummer ein, antwortet der Empfänger mit <math>A</math> und erwartet danach die andere Nummer. Trifft die andere Nummer ein, ist das Paket eine Wiederholung: Er antwortet mit <math>D</math> und bleibt im selben Zustand.
 
{| class="wikitable" style="text-align:center"
|+ style="white-space:nowrap" | Übergangsfunktion <math>\delta(q; a)</math> (Folgezustand)
! <math>\delta</math> !! <math>0</math> !! <math>1</math>
|-
| <math>\rightarrow {}^*q_0</math> || <math>q_1</math> || <math>q_0</math>
|-
| <math>{}^*q_1</math> || <math>q_1</math> || <math>q_0</math>
|}
 
{| class="wikitable" style="text-align:center"
|+ style="white-space:nowrap" | Ausgabefunktion <math>\lambda(q; a)</math> (Ausgabezeichen)
! <math>\lambda</math> !! <math>0</math> !! <math>1</math>
|-
| <math>\rightarrow {}^*q_0</math> || <math>A</math> || <math>D</math>
|-
| <math>{}^*q_1</math> || <math>D</math> || <math>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>0110</math> durchläuft der Automat:
 
:<math>q_0 \xrightarrow{0 / A} q_1 \xrightarrow{1 / A} q_0 \xrightarrow{1 / D} q_0 \xrightarrow{0 / A} q_1</math>


# q0 liest H: Die Kante <code>H / N</code> gibt N aus, der Automat bleibt in q0.
Die Ausgabe ist <math>AADA</math>: Das wiederholte Paket wird als Duplikat erkannt, alle anderen werden angenommen.
# q0 liest M: Die Kante <code>M / N</code> gibt N aus, der Automat wechselt nach q1.
# q1 liest M: Die Kante <code>M / N</code> gibt N aus, der Automat bleibt in q1.
# q1 liest H: Die Kante <code>H / B</code> gibt B aus, der Automat wechselt nach q0.


Die Ausgaben in dieser Reihenfolge ergeben das Ausgabewort <code>NNNB</code>. 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. Das Java-Programm im Abschnitt [[#Umsetzung in Java|Umsetzung in Java]] liefert für HMMH dieselbe Ausgabe.
Der Automat erfüllt die Anforderungen an ein [[#Kommunikationsprotokolle|Kommunikationsprotokoll]]: In jedem Zustand ist für jede Paketnummer genau eine Antwort festgelegt, auch für die unerwartete.


===Bonbonautomat als Moore-Automaten darstellen===
===Bonbonautomat als Moore-Automaten darstellen===
[[Datei:Moore-Automat Bonbonautomat.png|mini|Bonbonautomat als Moore-Automat]]
[[Datei:Moore-Automat Bonbonautomat.png|mini|Bonbonautomat als Moore-Automat]]
Beim Moore-Automaten steht die Ausgabe im Zustand. Die Zustände heißen q0/N, q1/N und q2/B: Der Name nennt den Zustand und seine Ausgabe.
Beim Moore-Automaten steht die Ausgabe im Zustand. Die Zustände heißen <math>q_0/N</math>, <math>q_1/N</math> und <math>q_2/B</math>: Der Name nennt den Zustand und seine Ausgabe.
* q0/N: keine Münze eingeworfen, Ausgabe N
* <math>q_0/N</math>: keine Münze eingeworfen, Ausgabe <math>N</math>
* q1/N: Münze eingeworfen, Ausgabe N
* <math>q_1/N</math>: Münze eingeworfen, Ausgabe <math>N</math>
* q2/B: Bonbon wird ausgegeben, Ausgabe B
* <math>q_2/B</math>: Bonbon wird ausgegeben, Ausgabe <math>B</math>
 
Der Moore-Automat hat drei statt zwei Zustände. Der Grund: Beim Mealy-Automaten führen nach <math>q_0</math> Kanten mit den Ausgaben <math>N</math> und <math>B</math>. Der Zustand „keine Münze“ wird deshalb für jede der beiden Ausgaben einmal angelegt, als <math>q_0/N</math> und als <math>q_2/B</math>. Nach <math>q_1</math> führen nur Kanten mit der Ausgabe <math>N</math>, dieser Zustand wird einmal angelegt. Startzustand ist <math>q_0/N</math>: Als Anfangsausgabe wird <math>N</math> festgelegt, denn vor dem ersten Zeichen gibt es kein Bonbon. Den Zustand <math>q_0/N</math> gibt es schon, ein weiterer Zustand ist nicht nötig.
 
Der Hebel nach der Münze führt von <math>q_1/N</math> nach <math>q_2/B</math> und gibt dort <math>B</math> aus. Beim Mealy-Automaten genügt dafür die Kante <code>H / B</code>. Von <math>q_2/B</math> führt <math>M</math> nach <math>q_1/N</math> und <math>H</math> nach <math>q_0/N</math>, genau wie von <math>q_0/N</math>. Alle drei Zustände sind Endzustände und deshalb Doppelkreise.
 
Für die Eingabe <math>HMMH</math> durchläuft der Moore-Automat diese Zustände:
 
:<math>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>NNNNB</math>: fünf Zeichen für vier Eingabezeichen. Ohne die Anfangsausgabe bleibt <math>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|Empfänger eines Protokolls als Mealy-Automaten entwerfen]] wird in einen Moore-Automaten umgewandelt.
 
'''Schritt 1: Zustände anlegen.''' Nach <math>q_0</math> führen die Kanten <code>1 / D</code> (von <math>q_0</math>) und <code>1 / A</code> (von <math>q_1</math>). Der Zustand wird deshalb zweimal angelegt: als <math>q_0/A</math> und als <math>q_0/D</math>. Nach <math>q_1</math> führen die Kanten <code>0 / A</code> (von <math>q_0</math>) und <code>0 / D</code> (von <math>q_1</math>). Es entstehen <math>q_1/A</math> und <math>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>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>N</math> (noch keine Quittung) festgelegt. Keine Kante führt mit der Ausgabe <math>N</math> nach <math>q_0</math>. Der Startzustand <math>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>q_0</math> entstanden sind, haben dieselben Kanten: <math>0</math> führt nach <math>q_1/A</math>, <math>1</math> nach <math>q_0/D</math>. Von den beiden Zuständen, die aus <math>q_1</math> entstanden sind, führt <math>0</math> nach <math>q_1/D</math> und <math>1</math> nach <math>q_0/A</math>.
 
{| class="wikitable" style="text-align:center"
! <math>\delta</math> !! <math>0</math> !! <math>1</math>
|-
| <math>\rightarrow {}^*q_0/N</math> || <math>q_1/A</math> || <math>q_0/D</math>
|-
| <math>{}^*q_0/A</math> || <math>q_1/A</math> || <math>q_0/D</math>
|-
| <math>{}^*q_0/D</math> || <math>q_1/A</math> || <math>q_0/D</math>
|-
| <math>{}^*q_1/A</math> || <math>q_1/D</math> || <math>q_0/A</math>
|-
| <math>{}^*q_1/D</math> || <math>q_1/D</math> || <math>q_0/A</math>
|}
 
Der Moore-Automat hat fünf Zustände, der Mealy-Automat zwei. In den Startzustand <math>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>0110</math> durchläuft der Moore-Automat diese Zustände:
 
:<math>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>NAADA</math>: die Anfangsausgabe <math>N</math>, danach das Ausgabewort <math>AADA</math> des Mealy-Automaten.
 
===Bonbonautomat in Java umsetzen===
Das Programm setzt den Bonbonautomaten nach dem Abschnitt [[#Umsetzung in Java|Umsetzung in Java]] um. Die Zustände <math>q_0</math> und <math>q_1</math> haben die Nummern 0 und 1, die Eingaben <math>M</math> und <math>H</math> die Spalten 0 und 1.
 
<syntaxhighlight lang="java">
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"));
    }
}
</syntaxhighlight>
 
Die Methode <code>lies</code> verarbeitet ein Zeichen, die Methode <code>verarbeite</code> ein ganzes Eingabewort. Das Programm gibt für <math>HMMH</math> das Ausgabewort <math>NNNB</math> aus und für <math>MH</math> das Ausgabewort <math>NB</math>. Für jede Eingabefolge wird ein neues Objekt erzeugt, damit der Automat wieder in <math>q_0</math> beginnt.


Der Moore-Automat hat drei statt zwei Zustände, weil das Bonbon einen eigenen Zustand braucht: Der Hebel nach der Münze führt von q1/N nach q2/B und gibt dort B aus. Beim Mealy-Automaten genügt dafür die Kante <code>H / B</code>. Von q2/B führt M nach q1/N und H nach q0/N.
Das Programm setzt voraus, dass die Eingabe nur die Zeichen <math>M</math> und <math>H</math> enthält: Die Methode <code>lies</code> behandelt jedes Zeichen, das nicht <code>M</code> ist, wie <code>H</code>. Soll das Programm fremde Zeichen erkennen, muss es sie vor der Verarbeitung prüfen und zum Beispiel mit einer Fehlermeldung abweisen.


[[Kategorie:Automaten]]
[[Kategorie:Automaten]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:AHR I Informatik LK]]