www.wikidata.de-de.nina.az

Mealy Automat Ein ist ein deterministischer endlicher Automat dessen Ausgabe von seinem Zustand und seiner Eingabe abhän

Mealy-Automat

Ein Mealy-Automat ist ein deterministischer endlicher Automat, dessen Ausgabe von seinem Zustand und seiner Eingabe abhängt; in der Veranschaulichung wird jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet. Der Name geht auf den Mathematiker George H. Mealy zurück.

Formale Definition Bearbeiten

Ein Mealy-Automat kann als 7-Tupel definiert werden:

  1. ist eine endliche Menge von Zuständen (). Statt wird oft auch verwendet.
  2. ist das Eingabealphabet, .
  3. ist das Ausgabealphabet, .
  4. ist die Übergangsfunktion.
  5. ist die Ausgabefunktion.
    Gelegentlich wird eine kompaktere Notation gewählt und beide Funktionen zu einer Zustandsübergangsfunktion zusammengefasst.
  6. ist der Startzustand. Statt wird oft auch oder verwendet. Dieser Startzustand wird mit einer doppelten Umrandung bzw. einem Doppelpfeil gekennzeichnet.
  7. ist eine (endliche) Menge möglicher akzeptierender Zustände (= Endzustandsmenge).

Wenn die reguläre Sprache des Automaten uninteressant ist, kann auch weggelassen werden. Dann wird der Automat als 6-Tupel definiert.

Beispiel Bearbeiten

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 Bearbeiten

Die Ausgabe eines Moore-Automaten hängt im Gegensatz zum Mealy-Automaten nicht von seiner Eingabe ab. 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 Bearbeiten

Literatur Bearbeiten

  • G. H. Mealy: A Method for Synthesizing Sequential Circuits, Bell System Tech. J. 34, pp. 1045–1079, September 1955.
  • Fricke, Digitaltechnik, Kapitel 8 "Synchrone Schaltwerke" bis inklusive 8.4. ISBN 978-3-8348-1783-9
  • Reichardt, Lehrbuch Digitaltechnik, Kapitel 12 "Entwurf synchroner Zustandsautomaten". ISBN 978-3-11-047800-6
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Mealy Automat ist ein deterministischer endlicher Automat dessen Ausgabe von seinem Zustand und seiner Eingabe abhangt in der Veranschaulichung wird jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet Der Name geht auf den Mathematiker George H Mealy zuruck Inhaltsverzeichnis 1 Formale Definition 2 Beispiel 3 Zusammenhang mit Moore Automat 4 Siehe auch 5 LiteraturFormale Definition BearbeitenEin Mealy Automat kann als 7 Tupel A Q S W d l q 0 F displaystyle mathcal A left Q Sigma Omega delta lambda q 0 F right nbsp definiert werden Q displaystyle Q nbsp ist eine endliche Menge von Zustanden Q lt displaystyle left Q right lt infty nbsp Statt Q displaystyle Q nbsp wird oft auch Z displaystyle Z nbsp verwendet S displaystyle Sigma nbsp ist das Eingabealphabet S lt displaystyle left Sigma right lt infty nbsp W displaystyle Omega nbsp ist das Ausgabealphabet W lt displaystyle left Omega right lt infty nbsp d Q S Q displaystyle delta colon Q times Sigma rightarrow Q nbsp ist die Ubergangsfunktion l Q S W displaystyle lambda colon Q times Sigma rightarrow Omega nbsp ist die Ausgabefunktion Gelegentlich wird eine kompaktere Notation gewahlt und beide Funktionen zu einer Zustandsubergangsfunktion z Q S W Q displaystyle zeta colon Q times Sigma rightarrow Omega times Q nbsp zusammengefasst q 0 Q displaystyle q 0 in Q nbsp ist der Startzustand Statt q 0 displaystyle q 0 nbsp wird oft auch z 0 displaystyle z 0 nbsp oder S 0 displaystyle S 0 nbsp verwendet Dieser Startzustand wird mit einer doppelten Umrandung bzw einem Doppelpfeil gekennzeichnet F Q displaystyle F subseteq Q nbsp ist eine endliche Menge moglicher akzeptierender Zustande Endzustandsmenge Wenn die regulare Sprache des Automaten uninteressant ist kann auch weggelassen werden Dann wird der Automat als 6 Tupel definiert Beispiel BearbeitenDer durch das folgende Zustandsdiagramm beschriebene Automat gibt seine Eingabe verzogert 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 zusatzlich zum Wechsel des Zustands eine Eins ausgegeben wird S bezeichnet den jeweiligen Zustand nbsp Zusammenhang mit Moore Automat BearbeitenDie Ausgabe eines Moore Automaten hangt im Gegensatz zum Mealy Automaten nicht von seiner Eingabe ab 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 schreibenFur jede Kante wird die Ausgabe in den Zustand ubertragen auf dem die Kante endet Hierbei stehen in der Regel verschiedene Ausgabewerte in einem Zustandsknoten nbsp Schritt 2 Knoten aufspalten und eingehende Kanten umhangenDie Zustande werden vervielfacht so dass jedem Zustand nur noch hochstens ein Ausgabewert zugeordnet ist anschliessend hangt man eingehende Kanten entsprechend der Ausgabewerte auf die neuen Zustande um nbsp Schritt 3 Ausgehende Kanten vervielfachenZuletzt muss man alle ausgehenden Kanten der ursprunglichen Zustande kopieren und an die Zustande aus Schritt 2 anhangen nbsp Die Ausgabe des so konstruierten Moore Automaten ist aquivalent zu der des ursprunglichen Mealy Automaten nbsp Siehe auch BearbeitenMoore Automat Deterministischer endlicher AutomatLiteratur BearbeitenG H Mealy A Method for Synthesizing Sequential Circuits Bell System Tech J 34 pp 1045 1079 September 1955 Fricke Digitaltechnik Kapitel 8 Synchrone Schaltwerke bis inklusive 8 4 ISBN 978 3 8348 1783 9 Reichardt Lehrbuch Digitaltechnik Kapitel 12 Entwurf synchroner Zustandsautomaten ISBN 978 3 11 047800 6 Abgerufen von https de wikipedia org w index php title Mealy Automat amp oldid 231603896