Mealy-Automat

Mealy-Automat

Ein Mealy-Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore-Automaten) von seinem Zustand und 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.

Inhaltsverzeichnis

Formale Definition

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

  • Q ist eine endliche Menge von Zuständen (\left| Q \right| < \infty). Statt Q wird oft auch Z verwendet.
  • Σ ist das Eingabealphabet, \left| \Sigma \right| < \infty.
  • Ω ist das Ausgabealphabet, \left| \Omega \right| < \infty.
  • \delta: Q \times \Sigma \rightarrow Q ist die Übergangsfunktion.
  • \lambda: Q \times \Sigma \rightarrow \Omega ist die Ausgabefunktion.
    Gelegentlich wird eine kompaktere Notation gewählt und beide Funktionen zu einer Zustandsübergangsfunktion \zeta: Q \times \Sigma \rightarrow \Omega \times Q zusammengefasst.
  • q_0 \in Q ist der Startzustand. Statt q0 wird oft auch z0 oder S0 verwendet. Dieser Startzustand wird mit einer doppelten Umrandung bzw. einem Doppelpfeil gekennzeichnet.
  • F \subseteq Q ist eine (endliche) Menge möglicher akzeptierter Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes w \in \Sigma^* in einem Zustand aus F hält, so gehört w zur Sprache L\left(A\right). Statt F wird oft auch A verwendet. Teilweise wird auch komplett auf F 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.

Ein Mealy-Automat mit Startzustand S0

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.

Der Automat aus dem Beispiel mit Ausgabe in den Knoten

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.

Der Automat mit zusätzlichen Zuständen

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.

Der Automat mit kopierten Kanten

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

Der fertige Moore-Automat

Siehe auch

Literatur

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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mealy Automat — Mealy o automatas statusas T sritis automatika atitikmenys: angl. Mealy automaton vok. Mealy Automat, m rus. автомат Мили, m pranc. automate Mealy, m ryšiai: sinonimas – Milio automatas …   Automatikos terminų žodynas

  • Mealy Automat — Ein Mealy Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore Automat) von seinem Zustand und seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird. Der… …   Deutsch Wikipedia

  • Mealy automaton — Mealy o automatas statusas T sritis automatika atitikmenys: angl. Mealy automaton vok. Mealy Automat, m rus. автомат Мили, m pranc. automate Mealy, m ryšiai: sinonimas – Milio automatas …   Automatikos terminų žodynas

  • Mealy'o automatas — statusas T sritis automatika atitikmenys: angl. Mealy automaton vok. Mealy Automat, m rus. автомат Мили, m pranc. automate Mealy, m ryšiai: sinonimas – Milio automatas …   Automatikos terminų žodynas

  • Automat (Informatik) — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • automate Mealy — Mealy o automatas statusas T sritis automatika atitikmenys: angl. Mealy automaton vok. Mealy Automat, m rus. автомат Мили, m pranc. automate Mealy, m ryšiai: sinonimas – Milio automatas …   Automatikos terminų žodynas

  • Moore Automat — Ein Moore Automat (benannt nach dem Mathematiker Edward F. Moore (1925 2003)) ist ein endlicher Automat, welcher deterministisch oder nichtdeterministisch sein kann. Im Gegensatz zum Mealy Automaten hängt seine Ausgabe ausschließlich von seinem… …   Deutsch Wikipedia

  • Moore-Automat — Ein Moore Automat (benannt nach dem Mathematiker Edward F. Moore (1925 2003)) ist ein endlicher Automat, welcher deterministisch oder nichtdeterministisch sein kann. Im Gegensatz zum Mealy Automaten hängt seine Ausgabe ausschließlich von seinem… …   Deutsch Wikipedia

  • Endlicher Automat — Abb. 1: Beispiel eines EA der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt… …   Deutsch Wikipedia

  • Abstrakter Automat — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”