HSG

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

Konvertierung eines Mealy-Automaten in einen Moore-Automaten

Autor: Frederik Stegner, MSS12 LK Inf-1 2003/04

Jeder Mealy-Automat kann durch Hinzufügen von Zuständen zu einem äqivalenten Moore-Atomaten gemacht werden.

Soweit die Theorie. Womit sich allerdings die Frage stellt: "Wie? Wenn ich einen Mealy-Automaten habe, wie mache ich dann aus ihm einen Moore-Automaten?"
Mit dieser Frage wollen wir uns heute beschäftigen. klingt komisch, is' aber so.

Hier sehen wir einen typischen Mealy-Automaten.
Seine (für unser Thema eigentlich unwichtige) Aufgabe: Prüfen, ob die zwei zuletzt eingegebenen Ausgaben gleich waren, je nach Ergebniss soll er ein Y oder ein N ausgeben (yes/no).
Doch halt! Ausgaben? Die hängen bei einem Moore-Automaten doch nur vom Zustand ab.
Deshalb muss man in einem Moore-Automaten ungleich mehr Zustände einbauen als in einem äquivalenten Mealy-Automaten.
Der Grund dafür ist, dass je nach der zu erfolgenden Ausgabe ein anderer Zustand angenommen wird.
Das heißt: Für einen Moore-Automaten braucht man für jeden Zustand des Mealy-Automaten so viele Zustände, wie es mögliche Ausgaben gibt.
Ein Moore-Automat benötigt also immer (nMealy-Zustände*nMealy-Ausgaben) Zustände.
Allerdings ist hier zu bedenken, dass einige unmögliche Kombinationen wegfallen können.

Und wie genau stellt man das jetzt an?

Es ist eigentlich ganz einfach, man nimmt sich den Mealy-Automaten und schreibt für jeden der vorhandenen Zustände soviele auf ein Blatt Papier, wie es mögliche Ausgaben gibt. Zur besseren Übersicht hängt man die ehemalige Ausgabe, die jetzt im Zustand gespeichert ist, mit einem Unterstrich _ an den entsprechenden Zustand an. Grob sieht es für den obigen Automaten etwa so aus: Die Verbindungsstriche ergeben sich, indem man für jeden Zustand die möglichen Eingaben ermittelt und prüft, welche Ausgaben beim Mealy-A. auftreten würden. Mittels dieser Ausgabe und dem Folgezustand im Mealy-A. bekommt man dann den Folgezustand im Moore-Automaten.

Ein fertiger, mit einem entsprechenden Programm erstelltes Zustandsdiagramm für einen Moore-Automaten sieht dann so aus:

Moore-Automat Mealy-Automat zum Vergleich

Fazit:

Wie man unschwer erkennen kann, sieht ein Moore-Automat weitaus komplizierter und aufwändiger aus und ist wahrscheinlich auch schwieriger zu verstehen, wenn man ein Zustandsdiagramm dafür vorgelegt bekäme.
Im realen Leben wird ein Moore-Automat wahrscheinlich auch mehr Einzelteile benötigen und mehr Geld kosten, weswegen ein Mealy-Automat eigentlich die bessere Wahl darstellt. Moore-Automaten haben bestimmt auch etwas Gutes, aber mir fällt gerade nichts ein, ich bin müde, muss noch für Deutsch lernen und wer hat jemals behauptet, dass Hausaufgaben objektiv sein müssen?