Mealy-Automat - LinkFang.de





Mealy-Automat


Ein Mealy-Automat ist ein endlicher Automat, dessen Ausgabe von seinem Zustand und (im Gegensatz zu einem Moore-Automaten) seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird. Der Name geht auf George H. Mealy zurück, der für die Verwendung dieser Ausprägung eintrat.

Formale Definition

Ein Mealy-Automat kann als 7-Tupel [math]\mathcal{A} = \left( Q, \Sigma, \Omega, \delta, \lambda, q_0, F \right)[/math] definiert werden:

  1. [math]Q[/math] ist eine endliche Menge von Zuständen ([math]\left| Q \right| \lt \infty[/math]). Statt [math]Q[/math] wird oft auch [math]Z[/math] verwendet.
  2. [math]\Sigma[/math] ist das Eingabealphabet, [math]\left| \Sigma \right| \lt \infty[/math].
  3. [math]\Omega[/math] ist das Ausgabealphabet, [math]\left| \Omega \right| \lt \infty[/math].
  4. [math]\delta: Q \times \Sigma \rightarrow Q[/math] ist die Übergangsfunktion.
  5. [math]\lambda: Q \times \Sigma \rightarrow \Omega[/math] ist die Ausgabefunktion.
    Gelegentlich wird eine kompaktere Notation gewählt und beide Funktionen zu einer Zustandsübergangsfunktion [math]\zeta: Q \times \Sigma \rightarrow \Omega \times Q[/math] zusammengefasst.
  6. [math]q_0 \in Q [/math] ist der Startzustand. Statt [math]q_0[/math] wird oft auch [math]z_0[/math] oder [math] S_0[/math] verwendet. Dieser Startzustand wird mit einer doppelten Umrandung bzw. einem Doppelpfeil gekennzeichnet.
  7. [math]F \subseteq Q[/math] ist eine (endliche) Menge möglicher akzeptierter Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes [math]w \in \Sigma^*[/math] in einem Zustand aus [math]F[/math] hält, so gehört [math]w[/math] zur Sprache [math]L\left(A\right)[/math]. Statt [math]F[/math] wird oft auch [math]A[/math] verwendet. Teilweise wird auch komplett auf [math]F[/math] verzichtet, und ob ein Wort Element der Sprache des Automaten ist, wird nur durch die Ausgabe bestimmt.

Beispiel

Der durch das folgende Zustandsdiagramm beschriebene Automat gibt seine Eingabe verzögert aus, d.h. zu einer Eingabe x0x1...xn erzeugt er die Ausgabe 0x0x1...xn-1. Hierbei bedeutet die Kantenbeschriftung 0/1, dass bei Eingabe einer Null zusätzlich zum Wechsel des Zustands eine Eins ausgegeben wird. S bezeichnet den jeweiligen Zustand.

Zusammenhang mit Moore-Automat

Mealy- und Moore-Automaten lassen sich ineinander umwandeln. Will man beispielsweise einen Mealy-Automaten in einen Moore-Automaten umwandeln kann man in folgenden drei Schritten vorgehen:

Schritt 1: Ausgabe in die Knoten schreiben

Für jede Kante wird die Ausgabe in den Zustand übertragen, auf dem die Kante endet. Hierbei stehen in der Regel verschiedene Ausgabewerte in einem Zustandsknoten.

Schritt 2: Knoten aufspalten und eingehende Kanten umhängen

Die Zustände werden vervielfacht, so dass jedem Zustand nur noch höchstens ein Ausgabewert zugeordnet ist; anschließend hängt man eingehende Kanten entsprechend der Ausgabewerte auf die neuen Zustände um.

Schritt 3: Ausgehende Kanten vervielfachen

Zuletzt muss man alle ausgehenden Kanten der ursprünglichen Zustände kopieren und an die Zustände aus Schritt 2 anhängen.

Die Ausgabe des so konstruierten Moore-Automaten ist äquivalent zu der des ursprünglichen Mealy-Automaten.

Siehe auch

Literatur

  • G. H. Mealy: A Method for Synthesizing Sequential Circuits, Bell System Tech. J. 34, pp. 1045–1079, September 1955.

Kategorien: Automatentheorie | Rechnerarchitektur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Mealy-Automat (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.