Zum Inhalt springen

Mealy-Automat

Aus FLBK-Wiki
Version vom 8. November 2026, 09:10 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (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>\…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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]\displaystyle{ A = (Q, \Sigma, \Omega, \delta, \lambda, q0, 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{ q0 \in Q }[/math]: Startzustand
  • [math]\displaystyle{ F \subseteq Q }[/math]: Menge der Endzustände

Oft ist 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 die Beschriftung Eingabe / Ausgabe. Zuerst steht das gelesene Zeichen, dann das ausgegebene. Zustände und Startpfeil werden wie beim DEA gezeichnet. Gilt [math]\displaystyle{ F = Q }[/math], entfällt der 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].

Arbeitsweise

Der Automat startet in q0. 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.

Moore-Automat

Beim Moore-Automaten hängt die Ausgabe nur vom Zustand ab: [math]\displaystyle{ \lambda: Q \to \Omega }[/math]. Die Ausgabe gehört zum erreichten Zustand und erscheint dadurch einen Schritt später als beim Mealy-Automaten.

Beide Modelle lassen sich ineinander umwandeln. Der Moore-Automat braucht oft mehr Zustände, weil jeder Zustand nur eine Ausgabe liefern kann.

Umsetzung in Java

Der Zustand wird als 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 Schleife liest das Eingabewort Zeichen für Zeichen. Sie hängt zuerst die Ausgabe an und wechselt dann den Zustand.

public class Bonbonautomat {
    // Zeilen: Zustaende q0, q1; Spalten: Eingaben M, H
    private static final int[][] DELTA = {{1, 0}, {1, 0}};
    private static final char[][] LAMBDA = {{'N', 'N'}, {'N', 'B'}};

    public static String uebersetze(String eingabe) {
        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) {
        System.out.println(uebersetze("HMMH"));
        System.out.println(uebersetze("MH"));
    }
}

Die Methode uebersetze liefert zu einem Eingabewort das Ausgabewort.

Beispiele

Bonbonautomat als Mealy-Automaten angeben

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.

  • [math]\displaystyle{ Q = \{q0, q1\} }[/math]
  • [math]\displaystyle{ \Sigma = \{M, H\} }[/math]
  • [math]\displaystyle{ \Omega = \{B, N\} }[/math]
  • [math]\displaystyle{ F = Q }[/math]

Die Übergangsfunktion [math]\displaystyle{ \delta }[/math] und die Ausgabefunktion [math]\displaystyle{ \lambda }[/math] stehen in zwei Tabellen:

δ M H
q0 q1 q0
q1 q1 q0
λ M H
q0 N N
q1 N B

Beispiel für das Lesen der Tabellen: Im Zustand q1 führt H zu [math]\displaystyle{ \delta(q1, H) = q0 }[/math] mit der Ausgabe [math]\displaystyle{ \lambda(q1, 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 HMMH. Der Lauf beginnt in q0.

  1. q0 liest H: Die Kante H / N gibt N aus, der Automat bleibt in q0.
  2. q0 liest M: Die Kante M / N gibt N aus, der Automat wechselt nach q1.
  3. q1 liest M: Die Kante M / N gibt N aus, der Automat bleibt in q1.
  4. q1 liest H: Die Kante H / B gibt B aus, der Automat wechselt nach q0.

Die Ausgaben in dieser Reihenfolge ergeben das Ausgabewort NNNB. 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 liefert für HMMH dieselbe Ausgabe.

Bonbonautomat als Moore-Automaten darstellen

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.

  • q0/N: keine Münze eingeworfen, Ausgabe N
  • q1/N: Münze eingeworfen, Ausgabe N
  • q2/B: Bonbon wird ausgegeben, Ausgabe B

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 H / B. Von q2/B führt M nach q1/N und H nach q0/N.