Mealy-Automat
Du hast das Wort Mealy-Automat gelesen und weißt überhaupt nicht, was das sein soll? In diesem Beitrag und im Video zeigen wir dir die wichtigsten Eigenschaften und die Funktionsweise mit Hilfe eines ausführlichen Beispiels.
Unter einem Mealy-Automaten, benannt nach dem Mathematiker George Mealy, versteht man in der theoretischen Informatik einen endlichen Automaten mit Ausgabe. Hierbei gilt, dass die Eingabe, anders als beim Moore-Automaten , zusammen mit dem aktuellen Zustand die Ausgabe bestimmt.
Inhaltsübersicht
Mealy-Automaten: Formale Definition
Mealy-Automaten können formal folgendermaßen definiert werden.
M = (Z, A, Ω, δ, λ, Zstart)
- Z ist die endliche Menge der Zustände des Automaten.
- A ist das Eingabe- und das Ausgabealphabet.
- δ stellt die Übergangsfunktion
- und λ die Ausgabefunktion da.
- Zu guter Letzt wird der Startzustand mit Zstart beschrieben.
Hierbei nicht vergessen, dass die Zeichen für die verschiedenen Elemente des Tupels variieren können. Vielleicht kennst du jeweils andere Bezeichner.
Mealy-Automat Beispiel
Wie wir bereits am Anfang geklärt haben, hängt die Ausgabe eines Mealy-Automaten nicht nur vom aktuellen Zustand, sondern auch von der Eingabe ab. Doch was heißt das konkret?
Schauen wir uns hierzu folgenden Automaten an:
Bis auf die veränderte Aufschrift auf den Zustandsübergängen sollte dir alles bekannt vorkommen. Wenn nicht, dann schau dir einfach unsere Videos zu endlichen Automaten oder nichtdeterministischen Automaten an. Doch was bedeutet nun die Aufschrift auf den Zustandsübergängen? Ganz einfach! Links vom Schrägstrich steht das ganz normale Eingabezeichen, wie du es bereits kennst. Rechts vom Schrägstrich kommt nun die Ausgabe hinzu, die beim Zustandsübergang ausgegeben wird.
Schauen wir uns das hier einmal genauer an: von Zustand z2 zu Zustand z0 gelangen wir bei einer null als Eingabe. Wird dieser Zustandsübergang ausgeführt, so gibt der Automat eine „1“ aus. Allgemein wird dies also als Eingabe – Schrägstrich – Ausgabe notiert. Versuchen wir doch einfach mal den Automaten in eine Automatentafel zu schreiben.
Automatentafel
Da das Alphabet des Automaten aus 0 und 1, also aus zwei Zeichen besteht, benötigen wir für jeden Zustand zwei Zeilen, eine für die 0 und eine für die 1 als Eingabe.
Jetzt können wir die Folgezustände eintragen. Wir suchen uns hierzu einen Zustand, zum Beispiel z0, aus und testen die Eingabe 1. In unserem Zustandsübergangsdiagramm sehen wir für diese Kombination als Folgezustand den Zustand z1. Das machen wir für alle Zeilen der Tabelle und erhalten die Folgezustände. Als letztes müssen wir lediglich für alle Zustandsübergänge die Ausgaben eintragen. Wir betrachten hierzu die erste Zeile der Tabelle. In unserem Zustandsübergangsdiagramm sehen wir, dass bei Zustand z0 für die Eingabe 0 eine 1 ausgegeben wird. Also schreiben wir dies in die Ausgabenspalte der Tabelle. Wenn wir das für alle Zeilen gemacht haben sind wir fertig. Super!
Mealy in Moore-Automat umwandeln
Zum Abschluss solltest du noch wissen, dass man Mealy-Automaten in Moore-Automaten umwandeln kann. Das Ganze kann ganz einfach durch das Hinzufügen neuer Zustände erzeugt werden. Es funktioniert aber auch umgekehrt vom Moore- zum Mealy-Automat .
Wir wollen zunächst damit beginnen, wie man einen Mealy- in einen Moore-Automat umwandeln kann. Das gelingt uns in den folgenden drei Schritten.
Verschieben der Zustandsübergänge in Zustände
Als erstes müssen wir die Ausgaben von den Zustandsübergängen in die Zustände selbst verschieben.
Schau dir dazu diesen Automaten einmal genauer an:
Du siehst, dass die Ausgabe des Automaten von der Eingabe, und nicht nur vom aktuellen Zustand abhängt, also handelt es sich hier um einen Mealy-Automaten . Woran sieht man das? Die Ausgaben stehen nicht in den Zuständen, sondern direkt auf den Zustandsübergängen!
Um diesen in einen Moore-Automaten umzuwandeln, müssen wir die Ausgaben von den Zustandsübergängen in die Zustände verschieben. Hier müssen wir manche Zustände zweiteilen, sodass jeder Zustand nur noch für höchstens ein Ausgabezeichen verantwortlich ist.
Wir beginnen mit dem Startzustand. Die Zustandsübergänge, die von z0 ausgehen, liefern beide ein „x“ als Ausgabe. Wir können also die Zustände z1 und z2 hinzufügen, und sie mit dem Ausgabewert „x“ versehen, und dann mit dem Startzustand verbinden. Da die Zustände ab jetzt für die Ausgabe zuständig sind, müssen wir auf die Zustandsübergänge nur die Eingabe schreiben. Super! Als nächstes sehen wir, dass die Zustände z1 und z2 mit Zustandsübergängen verbunden sind, die ebenfalls ein „x“ als Ausgabe liefern. Wir können also z1 und z2 jeweils miteinander verbinden, da beiden Zuständen das „x“ bereits als Ausgabe zugeteilt wurde.
Jetzt stoßen wir auf unser erstes Problem: die Zustände z1 und z2 haben im Mealy-Automaten einen Zustandsübergang zu sich selbst, der als Ausgabe ein „y“ liefert. Problematisch ist jetzt, dass wir noch keinen Zustand haben, der ein „y“ als Ausgabe bereitstellt. Um das Problem zu beheben, benennen wir zuerst unsere alten Zustände „z1“ und „z2“ mit der Ausgabe „x“ zu „z1x“ und „z2x“ um. Jetzt können wir zwei neue Zustände einführen, die als Ausgabe „y“ liefern und nennen diese „z1y“ und „z2y“.
Rückweg in den Automaten
Das Einzige was uns jetzt noch fehlt, ist ein Weg von unseren neuen Zuständen zurück in den Automaten. Wir schließen aus unserem Mealy-Automaten vom Anfang, dass sich unsere beiden neuen Zustände „z1y“ und „z2y“ genau so verhalten müssen wie die Zustände „z1x“ und „z2x“. Wir fügen also den Übergang von „z1y“ zu „z2x“ bei Eingabe 0 und den Übergang von „z2y“ zu „z1x“ bei Eingabe 1 ein und sind somit fertig.