Ein Mealy-Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore-Automat) von seinem Zustand und seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird.

Formale Definition

---

Ein Mealy-Automat kann als 7-Tupel $\backslash mathcal\{A\}\; =\; \backslash left(\; Q,\; \backslash Sigma,\; \backslash Omega,\; \backslash delta,\; \backslash lambda,\; q\_0,\; F\; \backslash right)$ definiert werden:

• $Q$ ist eine endliche Menge von Zuständen (). Statt $Q$ wird oft auch $Z$ verwendet.
• $\backslash Sigma$ ist das Eingabealphabet. , $Q\; \backslash cap\; \backslash Sigma\; =\; \backslash empty$
• $\backslash Omega$ ist das Ausgabealphabet.
• $\backslash delta$ ist die Übergangsfunktion $\backslash delta\; :\; Q\; \backslash times\; \backslash Sigma\; \backslash rightarrow\; Q$
• $\backslash lambda$ definiert die Ausgabe: $\backslash lambda:\; Q\; \backslash times\; \backslash Sigma\; \backslash rightarrow\; \backslash Omega$
• $q\_0\; \backslash in\; Q$ ist der Startzustand. Statt $q\_0$ wird oft auch $z\_0$ oder $S\_0$ verwendet. Dieser Startzustand wird mit einer doppelten Umrandung bzw. eines Doppelpfeiles gekennzeichnet.
• $F\; \backslash subseteq\; Q$ ist eine (endliche) Menge möglicher akzeptierender Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes $w\; \backslash in\; \backslash Sigma^*$ in einem Zustand aus $F$ hält, so gehört w zur Sprache $L\backslash left(A\backslash right)$. Statt $F$ wird oft auch $A$ verwendet. Teilweise wird auch komplett auf $F$ verzichtet und ob ein Wort Element der Sprache des Automaten ist wird nur durch die Ausgabe bestimmt.

Beispiel

---

Der durch das folgende Zustandsdiagramm beschriebene Automat gibt seine Eingabe verzögert aus, d.h. zu einer Eingabe x₀x₁...x_n erzeugt er die Ausgabe 0x₀x₁...x_n-1. Hierbei bedeutet die Kantenbeschriftung 0/1, dass bei Eingabe einer Null zusätzlich zum Wechsel des Zustands eine Eins ausgegeben wird.

Mealy_automaton.png

Zusammenhang mit Moore-Automat

---

Mealy- und Moore-Automaten lassen sich ineinander umwandeln. Will man beispielsweise einen Mealy-Automaten in einen Moore-Automaten umwandeln kann man in folgenden drei Schritten vorgehen:

Schritt 1: Ausgabe in die Knoten schreiben

Für jede Kante wird die Ausgabe in den Zustand übertragen, auf dem die Kante endet. Hierbei stehen in der Regel verschiedene Ausgabewerte in einem Zustandsknoten.

mealy_automaton_to_moore1.png

Schritt 2: Knoten aufspalten und eingehende Kanten umhängen

Die Zustände werden vervielfacht, so dass jedem Zustand nur noch höchstens ein Ausgabewert zugeordnet ist; anschließend hängt man eingehende Kanten entsprechend der Ausgabewerte auf die neuen Zustände um.

mealy_automaton_to_moore2.png

Schritt 3: Ausgehende Kanten vervielfachen

Zuletzt muss man alle ausgehenden Kanten der ursprünglichen Zustände kopieren und an die Zustände aus Schritt 2 anhängen.

mealy_automaton_to_moore3.png

Die Ausgabe des so konstruierten Moore-Automaten ist äquivalent zu der des ursprünglichen Mealy-Automaten.

moore_automaton.png

Siehe auch

---

• Moore-Automat
• Deterministischer endlicher Automat

Literatur

---

• G. H. Mealy: A Method for Synthesizing Sequential Circuits, Bell System Tech. J. 34, pp. 1045–1079, September 1955.

Automatentheorie | Rechnerarchitektur

Mealyho automat | Mealy machine | ミーリ・マシン | Automat Mealy'ego | Mealy机