Theoretische Informatik

Mealy-Automat

Du hast das Wort Mealy-Automat gelesen und weißt überhaupt nicht was das sein soll? Kopf hoch, in diesem Beitrag zeigen wir dir die wichtigsten Eigenschaften und Funktionsweise mit Hilfe eines ausführlichen Beispiels. Viel Spaß!

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 kann man 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

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:

Mealy Automat
direkt ins Video springen
Mealy Automat

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.

Mealy Automat Beispiel
direkt ins Video springen
Mealy Automat Beispiel

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 diese 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:

Mealy in Moore
direkt ins Video springen
Mealy in Moore

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, so dass 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“.

Einzeichnen der neuen Zustandsübergänge

Wir zeichnen jetzt die Zustandsübergänge von „z1x“ und „z2x“ zu den neuen Zuständen ein und fügen dann noch die Zustandsübergänge zu sich selbst ein.

Mealy in Moore Automat umwandeln
direkt ins Video springen
Mealy- in Moore-Automat umwandeln

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.

 


Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.