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 $\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$).
• Σ ist das Eingabealphabet. $\left| \Sigma \right| < \infty$, $Q \cap \Sigma = \empty$
• Ω ist das Ausgabealphabet. $\left| \Omega \right| < \infty$
• δ ist die Übergangsfunktion $\delta : Q \times \Sigma \rightarrow Q$
• λ definiert die Ausgabe: $\lambda: Q \rightarrow \Omega$
• $q_0 \in Q$ ist der Startzustand.
• $F \subseteq Q$ ist eine (endliche) Menge möglicher akzeptierender Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes $J \in \Sigma^*$ in einem Zustand aus F hält, so gehört J zur Sprache $L\left(A\right)$.

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

Die Anzahl der Zustände eines Moore-Automaten ist größer-gleich der Anzahl der Zustände des entsprechenden Mealy-Automaten.

Beispiel

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

$Q = \lbrace q_0, \, q_1, \, q_2, \, q_3 \rbrace$,

$\Sigma = \lbrace x, \, y, \, z \rbrace$,

$\Omega = \lbrace a, \, b, \, c \rbrace$

und q₀ = q₀.

Die Übergangsfunktion δ sowie die Ausgabefunktion λ können durch einen Graphen bzw. eine Automatentafel dargestellt werden.

Darstellung von δ und λ durch Graphen:

Darstellung von δ und λ durch Automatentafel:

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

Wenn der Automat sich in Zustand q₁ befindet und von dort aus das Zeichen "x" oder das Zeichen "z" einliest, geht der Automat in Zustand q₃ über. Beim Erreichen des Zustandes q₃ 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:

Siehe auch

• Automatentheorie
• Mealy-Automat
• Medwedew-Automat
• Deterministischer endlicher Automat
• Nichtdeterministischer endlicher Automat