Moore-Automat - LinkFang.de





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 Zustand ab. Beim Erreichen eines Zustandes wird eine Ausgabe erzeugt, welche unabhängig vom Übergang in diesen Zustand ist.

Formale Definition

Der Moore-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(\left| Q \right| \lt \infty\right)[/math].
  2. [math]\Sigma[/math] ist das Eingabealphabet. [math]\left| \Sigma \right| \lt \infty[/math], [math]Q \cap \Sigma = \empty[/math]
  3. [math]\Omega[/math] ist das Ausgabealphabet. [math]\left| \Omega \right| \lt \infty[/math]
  4. [math]\delta[/math] ist die Übergangsfunktion [math]\delta : Q \times \Sigma \rightarrow Q[/math]
  5. [math]\lambda[/math] definiert die Ausgabefunktion: [math]\lambda: Q \rightarrow \Omega[/math]
  6. [math]q_0 \in Q [/math] ist der Startzustand.
  7. [math]F \subseteq Q[/math] ist eine (endliche) Menge möglicher akzeptierender Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes [math]J \in \Sigma^*[/math] in einem Zustand aus [math]F[/math] hält, so gehört [math]J[/math] zur Sprache [math]L\left(A\right)[/math].

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

Die Anzahl der Zustände eines Moore-Automaten ist nicht kleiner als die Anzahl der Zustände des entsprechenden Mealy-Automaten.

Digitaltechnik

Eine Realisierung des Moore-Automaten ist mittels Digitaltechnik möglich. Hierfür sind zwei Schaltnetze und ein getakteter Speicherblock erforderlich. Neben den auf einer Leiterplatte verdrahteten Logikbausteinen erfolgt die Umsetzung häufig mittels programmierbarer Logik und Anwendung einer Hardwarebeschreibungssprache.

Die Verarbeitung mit Logikschaltkreisen erfordert die Umwandlung des Ein- und Ausgabealphabets in einen Binärcode analog der nachfolgenden Tabelle.

Codierung
Eingabealphabet e0 e1 e2
x 0 1 0
y 0 0 1
Zustandsmenge d0 d1 d2
q0 1 1 0
q1 1 0 1
Ausgabealphabet a0 a1
a 0 1
b 1 0

Beschreibung eines Automaten

Gegeben sei ein durch ein 6-Tupel [math]\left( Q, \Sigma, \Omega, \delta, \lambda, q_0\right)[/math] definierter, deterministischer endlicher Automat mit

[math]Q = \lbrace q_0, \, q_1, \, q_2, \, q_3 \rbrace [/math],

[math] \Sigma = \lbrace x, \, y, \, z \rbrace [/math],

[math] \Omega = \lbrace a, \, b, \, c \rbrace [/math]

und [math]q_0 = q_0[/math].

Die Übergangsfunktion [math]\delta[/math] sowie die Ausgabefunktion [math]\lambda[/math] können durch einen Graphen bzw. eine Automatentafel dargestellt werden.

Beschreibung eines Automaten
[math]\delta[/math] (Übergang)↘   [math]x[/math]     [math]y[/math]     [math]z[/math]   [math]\lambda[/math] (Ausgabe)
q0 [math]q_3[/math] [math]q_3[/math] [math]q_1[/math] [math]b[/math]
q1 [math]q_3[/math] [math]q_2[/math] [math]q_3[/math] [math]a[/math]
q2 - [math]q_3[/math] - [math]a[/math]
q3 [math]q_3[/math] - [math]q_2[/math] [math]c[/math]
Darstellung von [math]\delta[/math] und [math]\lambda[/math] durch Graphen Darstellung von [math]\delta[/math] und [math]\lambda[/math] durch Automatentafel

Sowohl dem Graphen als auch der Tabelle lassen sich nun Informationen wie die folgende entnehmen:

Wenn der Automat sich im Zustand [math]q_1[/math] befindet und von dort aus das Zeichen "x" oder das Zeichen "z" einliest, geht der Automat in den Zustand [math]q_3[/math] über. Beim Erreichen des Zustandes [math]q_3[/math] erfolgt die Ausgabe "c".

Überführung in einen Mealy-Automaten

Jeder Moore-Automat lässt sich sehr leicht in einen äquivalenten Mealy-Automaten überführen. Dazu muss lediglich das Ausgabesymbol des Zielzustandes mit auf die Transition (Zustandsübergang) geschrieben werden. Betrachten wir dazu das obige Beispiel, dann sieht die Überführung folgendermaßen aus:

Literatur

Siehe auch


Kategorien: Automatentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Moore-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.