Moore-Automat

Ein Moore-Automat ist ein endlicher Automat, dessen Ausgabe ausschließlich von seinem Zustand abhängt. Beim Erreichen eines Zustandes wird eine Ausgabe erzeugt, welche unabhängig vom Übergang in diesen Zustand ist. Moore-Automaten können deterministisch oder nichtdeterministisch sein. Sie sind nach dem Mathematiker Edward F. Moore (1925–2003) benannt.

Formale Definition

Der Moore-Automat kann als 7-Tupel ${\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\Omega ,\delta ,\lambda ,q_{0},F\right)}$ definiert werden:

1. ${\displaystyle Q}$ ist eine endliche Menge von Zuständen ${\displaystyle \left(\left|Q\right|<\infty \right)}$.
2. ${\displaystyle \Sigma }$ ist das Eingabealphabet. ${\displaystyle \left|\Sigma \right|<\infty }$
3. ${\displaystyle \Omega }$ ist das Ausgabealphabet. ${\displaystyle \left|\Omega \right|<\infty }$
4. ${\displaystyle \delta }$ ist die Übergangsfunktion ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$
5. ${\displaystyle \lambda }$ definiert die Ausgabefunktion: ${\displaystyle \lambda :Q\rightarrow \Omega }$
6. ${\displaystyle q_{0}\in Q}$ ist der Startzustand.
7. ${\displaystyle F\subseteq Q}$ ist eine (endliche) Menge möglicher akzeptierender Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes ${\displaystyle J\in \Sigma ^{*}}$ in einem Zustand aus ${\displaystyle F}$ hält, so gehört ${\displaystyle J}$ zur Sprache ${\displaystyle L\left(A\right)}$.

Wenn die reguläre Sprache des Automaten uninteressant ist, kann ${\displaystyle F}$ 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

Moore-Automat in der 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 ${\displaystyle \left(Q,\Sigma ,\Omega ,\delta ,\lambda ,q_{0}\right)}$ definierter, deterministischer endlicher Automat mit

${\displaystyle Q=\lbrace q_{0},\,q_{1},\,q_{2},\,q_{3}\rbrace }$,

${\displaystyle \Sigma =\lbrace x,\,y,\,z\rbrace }$,

${\displaystyle \Omega =\lbrace a,\,b,\,c\rbrace }$

und ${\displaystyle q_{0}=q_{0}}$.

Die Übergangsfunktion ${\displaystyle \delta }$ sowie die Ausgabefunktion ${\displaystyle \lambda }$ können durch einen Graphen bzw. eine Automatentafel dargestellt werden.

Beschreibung eines Automaten

${\displaystyle \delta }$ (Übergang)↘   ${\displaystyle x}$     ${\displaystyle y}$     ${\displaystyle z}$   ${\displaystyle \lambda }$ (Ausgabe) q0 ${\displaystyle q_{3}}$ ${\displaystyle q_{3}}$ ${\displaystyle q_{1}}$ ${\displaystyle b}$ q1 ${\displaystyle q_{3}}$ ${\displaystyle q_{2}}$ ${\displaystyle q_{3}}$ ${\displaystyle a}$ q2 - ${\displaystyle q_{3}}$ - ${\displaystyle a}$ q3 ${\displaystyle q_{3}}$ - ${\displaystyle q_{2}}$ ${\displaystyle c}$

Darstellung von ${\displaystyle \delta }$ und ${\displaystyle \lambda }$ durch Graphen

Darstellung von ${\displaystyle \delta }$ und ${\displaystyle \lambda }$ durch Automatentafel

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

Wenn der Automat sich im Zustand ${\displaystyle q_{1}}$ befindet und von dort aus das Zeichen ${\displaystyle x}$ oder das Zeichen ${\displaystyle z}$ einliest, geht der Automat in den Zustand ${\displaystyle q_{3}}$ über. Beim Erreichen des Zustandes ${\displaystyle q_{3}}$ erfolgt die Ausgabe ${\displaystyle c}$.

Medwedew-Automat

Grafik eines Medwedew-Automaten

Der Medwedew-Automat ist eine Sonderform des Moore-Automaten, bei dem die Zustände direkt die Ausgabe bilden, es also kein Ausgangsnetzwerk gibt. Somit ist jeder Medwedew-Automat ein Moore-Automat, aber nicht andersherum. Der Name geht auf Ju. T. Medwedew zurück, der einer Übersetzung von Automata Studies ins Russische einen eigenen Artikel anhängte.

Vorteile

• Die Ausgabe ist schneller.
• Die Taktflanke der Flipflops kann kleiner gestellt werden.

Überführung in einen Mealy-Automaten

Die Ausgabe eines Mealy-Automaten ist von seinem Zustand und seiner Eingabe abhängig. Jeder Moore-Automat lässt sich sehr leicht in einen äquivalenten Mealy-Automaten überführen. Dazu muss lediglich das Ausgabesymbol des Eingangszustandes 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

Literatur

• Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Eine anwendungsbezogene Einführung. Vieweg+Teubner, Wiesbaden 2011, ISBN 978-3-8348-1537-8 (eingeschränkte Vorschau in der Google-Buchsuche).