HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material

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 = {z0, z1, z2, z3};
  • Anfangszustand = z0;
  • Endzustände = {z3};
  • Eingabealphabet = {a, b, c}
  • Ausgabealphabet = {x, y}

Automatentafel

z0 z1 z2 z3
a z0 / x z3 / x z0 / y z0 / x
b z1 / y z1 / y z0 / y z2 / x
c z3 / x z2 / x z0 / y z2 / x


Die Übergangsfunktion bestimmt den Folgezustand, z.B. fü(z1,c) = z2 .
Die Ausgabefunktion bestimmt die Ausgabe, z.B. fa(z1,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.