Moore-Automat
Du willst wissen was genau ein Moore-Automat ist? Hier im Beitrag und im Video zeigen wir dir die formale Definition und zeigen dir den Aufbau anhand eines einfachen Aufgabenbeispiels. Zusätzlich erklären wir dir worin er sich vom Mealy-Automaten unterscheidet.
Unter einem Moore-Automaten, benannt nach dem Mathematiker Edward Forrest Moore, versteht man einen endlichen Automaten mit Ausgabe. Hierbei gilt, dass die Eingabe, anders als beim Mealy-Automaten, für die Ausgabe keine Rolle spielt. Moore-Automaten können sowohl deterministisch als auch nichtdeterministisch sein.
Inhaltsübersicht
Moore-Automaten: Formale Definition
Fangen wir damit an den Automaten formal zu definieren. Neben den üblichen Parametern kommen jetzt noch das Ausgabealphabet und eine Ausgabefunktion hinzu.
Doch schauen wir uns der Reihe nach an was wir alles benötigen:
Wir definieren einen Automaten N. Dieser hat die folgenden Eigenschaften:
- Eine endliche Menge an Zuständen Z,
- das Eingabealphabet E,
- das Ausgabealphabet Ω,
- die Übergangsfunktion δ,
- und die Ausgabefunktion λ.
Der Startzustand des Automaten wird mit Zstart dargestellt.
Denke hierbei daran, dass jeder Buchstabe nur ein Platzhalter ist, vielleicht kennst du die einzelnen Elemente mit anderen Buchstaben.
Es kann zu diesem Tupel auch noch die Menge der Endzustände Zend hinzugefügt werden. Diese werden jedoch bei sehr vielen Moore-Automaten überhaupt nicht gebraucht.
Moore-Automat Aufgabe
Wir betrachten nun zur Veranschaulichung, die folgendene Moore-Automat Aufgabe:
Hierbei ist der Automat M: M = (Z, E, Ω, δ, λ, Zstart).
Unsere Menge der Zustände Z besteht hierbei aus 4 Zuständen: Z = {z0, z1, z2, z3}. Unser Eingabealphabet sind die Buchstaben a, b und c: E = {a, b, c}, das Ausgabealphabet wird von den Zahlen 0, 1 und 2: Ω = {0, 1, 2} gebildet und unser Startzustand ist Zstart = z0. Die Übergangsfunktion und die Ausgabefunktion sind durch diese Tabelle gegeben:
Hierbei gibt es für dich nur eine Neuerung: Die Spalte λ. Falls du die Tabelle gar nicht verstehst, schau dir doch am besten unser Video zu deterministischen endlichen Automaten an.
Die Spalte Lambda ist folgendermaßen zu verstehen. Befinden wir uns in Zustand z1 und wechseln mit der Eingabe c in Zustand z2, dann erfolgt beim Eintritt in diesen Zustand die Ausgabe 2. Warum? Das schauen wir uns am besten am Zustandsübergangsdiagramm an:
In der unteren Hälfte der Zustände kannst du sehen, welches Zeichen beim Eintritt in den Zustand ausgegeben wird. Wir gehen also von z 0 über c nach z 2 und sehen die 2 als Ausgabe. Ganz einfach, oder?
Hier geht es zu einem noch ausführlicheren Beispiel. Darin zeigen wir dir, wie du mit einem Moore Automaten eine Ampelschaltung modellieren kannst.
Moore- und Mealy-Automat: Unterschied
Hast du schon mal etwas vom Mealy-Automat gehört? Dieser ist dem Moore-Automaten sehr ähnlich. Der eigentliche Hauptunterschied zwischen Moore- und Mealy-Automat ist, dass die Ausgaben des Moore-Automaten nur davon abhängen, in welchem Zustand er sich befindet.
Im Mealy-Automaten ist die Ausgabe sowohl mit dem Zustand als auch mit der aktuellen Eingabe verbunden.
Unterschied – Schaltwerk
Der Unterschied zwischen den Automaten wird schnell klar, wenn man beide als Schaltwerk betrachtet.
Wie du sofort erkennen kannst, ist der einzige Unterschied, dass die Eingabe beim Mealy-Automaten mit in die Entscheidung für eine Ausgabe einfließt, beim Moore-Automaten jedoch nicht.
Moore-Automat Beispiel
In diesem Absatz erklären wir dir nach einer kurzen Wiederholung, ein ausführliches Moore-Automat Beispiel anhand einer Ampel. Hier zeigen wir dir Schritt-für-Schritt den Aufbau anhand einer Automatentaffel und eines Zustandsdiagramms. Los geht’s!
Um den Beitrag verstehen zu können, solltest du bereits die Elemente eines Moore-Automaten kennen. Diese sind neben den üblichen Zuständen Z, dem Eingabealphabet E, der Übergangsrelation Delta und den Start- und Endzuständen noch das Ausgabealphabet Omega und die Ausgabefunktion Lambda. Außerdem solltest du wissen, was eine Automatentafel ist. All das erklären wir dir im Video zum Moore-Automat.
Moore-Automat Beispiel: Ampel
Wir wollen den Moore-Automaten nun verwenden, um eine Ampelschaltung zu modellieren. Dafür brauchen wir zunächst eine Möglichkeit jede mögliche Ampelphase mit Zahlen darzustellen. Das gelingt uns mit einer dreistelligen Binärzahl. Die erste Ziffer steht dann für Rot, die zweite für Gelb und die dritte für Grün.
Ist die jeweilige Ziffer eine 1, dann ist die Farbe aktiv, ist sie 0, dann ist die Farbe nicht aktiv. Das Ganze sieht dann folgendermaßen aus:
Nun brauchen wir unsere Zustände, und zwar für jede Ampelphase einen eigenen. Grün ist Zustand z0, unser Startzustand. Gelb bekommt Zustand z1, Gelb-Rot z2 und zu guter Letzt Rot z3. Damit können wir die Automatentafel erstellen.
Moore Automat – Ampel: Automatentafel & Zustandsübergangsdiagramm
Als erstes können wir die Ausgaben, die bei Erreichen der jeweiligen Zustände ausgegeben werden sollen, in die Tabelle einfügen. Hierzu benutzen wir unsere binäre Codierung von vorhin, also zum Beispiel 001 für Grün.
Als nächstes definieren wir unsere Zustandsübergänge. Wenn eine Ampel auf Grün steht, dann kann sie entweder grün bleiben oder auf gelb wechseln. Steht sie auf gelb, dann wechselt sie als nächstes auf Rot. Dort verharrt sie wieder eine Weile und schaltet dann auf gelb-rot und anschließend wieder auf grün. Die Abfolge müssen wir nun in einer sinnvollen Schreibweise darstellen.
Dafür legen wir zuerst fest, dass die Ampel, wenn sie grün ist, mit der Eingabe 0 im aktuellen Zustand bleibt Das gleiche passiert bei der Eingabe 1, wenn die Ampel aktuell rot ist. Mit der jeweils anderen Eingabe soll in den Folgezustand gewechselt werden, also mit einer 1 von Grün zu Gelb und mit einer 0 von Rot zu Gelb-Rot. Die restlichen Übergänge verhalten sich bei jeder Eingabe gleich. Gelb wechselt sowohl bei einer 0 als auch bei einer 1 zu Rot und Gelb-Rot wechselt analog zu Grün.
Als Zustandsübergangsdiagramm sieht das Ganze dann so aus:
Sehr gut! Jetzt kennst du dich mit Moore-Automaten bestens aus und kannst sogar schon kompliziertere Automaten modellieren.
Überführung zum Mealy-Automaten
Wegen ihrer Ähnlichkeit, lassen sich der Moore- und Mealy-Automat einfach ineinander überführen. In unserem Beitrag zum Mealy-Automat erfährst du, wie man einen Mealy-Automaten in einen Moore-Automaten umwandeln kann. Nun sehen wir uns aber an, wie die Überführung in einen Mealy-Automat funktioniert.
Sehen wir uns dafür die Zustandsübergangsdiagramme der folgenden Beispiele an, die exemplarisch eine Überführung darstellen:
Hierbei werden die Ausgabesymbolde des Zielzustands auf die entsprechenden Zustandsübergänge umgeschrieben.