Darstellungsarten eines endlichen Automaten

Automatengraph

Die Grafik wurde ursprünglich mit Charon erzeugt und mit PaintShopPro nachbearbeitet. (Charon sieht keine Ausgaben vor und trennt Mehrfacheingaben durch "/" statt durch ",")

Am Graphen kann man ablesen:

Zustände = {z₀, z₁, z₂, z₃};
Anfangszustand = z₀;
Endzustände = {z₃};
Eingabealphabet = {a, b, c}
Ausgabealphabet = {x, y}

Automatentafel

	z₀	z₁	z₂	z₃
a	z₀ / x	z₃ / x	z₀ / y	z₀ / x
b	z₁ / y	z₁ / y	z₀ / y	z₂ / x
c	z₃ / x	z₂ / x	z₀ / y	z₂ / x

Die Übergangsfunktion bestimmt den Folgezustand, z.B. f_ü(z₁,c) = z₂ .
Die Ausgabefunktion bestimmt die Ausgabe, z.B. f_a(z₁,c) = x .

Moore- und Mealy-Automaten

Der oben angeführte Automat ist ein sogenannter Mealy-Automat. Hier hängt die Ausgabe vom Zustand und der Eingabe ab. Der Automat heißt auch Transduktor. Wird die Ausgabe mit dem aktuellen Zustand assoziiert, so ist der Automat ein Moore-Automat.
Jeder Mealy-Automat kann durch Hinzufügen von Zuständen zu einem äqivalenten Moore-Atomaten gemacht werden. Dabei wird jede mögliche Ausgabe (z.B. x, y) beim Erreichen eines Zustands (z.B. z2) zum Zustand hinzugenommen, im Beispiel wird z2 durch z2_x und z2_y ersetzt. Im Folgenden wird das Vorgehen am Beispiel des obigen Transduktors demonstriert:

Man sieht, dass die Zustände z1_x, z2_y und z3_y theoretisch nie erreicht werden. Sie können eigentlich weggelassen werden. In der Technik wird man für ein fehlerhaftes Hineingeraten ein systemgerechtes Weiterarbeiten vorsehen.