Quelltext der Seite Moore-Automat

Ein '''Moore-Automat''' 
ist ein [[endlicher Automat]], dessen [[Ausgabe (Computer)|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 [[Deterministischer endlicher Automat|deterministisch]] oder [[Nichtdeterministischer endlicher Automat|nichtdeterministisch]] sein. Sie sind nach dem Mathematiker [[Edward F. Moore]] (1925–2003) benannt.

== 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:
# <math>Q</math> ist eine endliche Menge von Zuständen <math>\left(\left| Q \right| < \infty\right)</math>.
# <math>\Sigma</math> ist das Eingabealphabet. <math>\left| \Sigma \right| < \infty</math>
# <math>\Omega</math> ist das Ausgabealphabet. <math>\left| \Omega \right| < \infty</math>
# <math>\delta</math> ist die Übergangsfunktion <math>\delta : Q \times \Sigma \rightarrow Q</math>
# <math>\lambda</math> definiert die Ausgabefunktion: <math>\lambda: Q \rightarrow \Omega</math>
# <math>q_0 \in Q </math> ist der Startzustand.
# <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-Automat]]en.

== Digitaltechnik ==
[[Datei:Moore-Automat-de.svg|mini|Moore-Automat in der Digitaltechnik]]
Eine Realisierung des Moore-Automaten ist mittels Digitaltechnik möglich. Hierfür sind zwei [[Schaltnetz]]e und ein getakteter Speicherblock erforderlich. Neben den auf einer Leiterplatte verdrahteten Logikbausteinen erfolgt die Umsetzung häufig mittels [[Programmierbare logische Schaltung|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'''
|

{|class="wikitable zebra" style="text-align:center;"
!Eingabealphabet !! e<sub>0</sub> !! e<sub>1</sub> !! e<sub>2</sub>
|----
| x || 0 || 1 || 0
|----
|y || 0 || 0 || 1
|----
|… || … || … || …
|}
|
{|class="wikitable zebra" style="text-align:center;"
!Zustandsmenge !! d<sub>0</sub> !! d<sub>1</sub> !! d<sub>2</sub>
|----
| q<sub>0</sub> || 1 ||1 || 0
|----
| q<sub>1</sub> || 1 || 0 || 1
|----
| … || … || … || …
|}
|
{|class="wikitable zebra" style="text-align:center;"
!Ausgabealphabet !!a<sub>0</sub> !!a<sub>1</sub>
|----
| 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 [[Zustandsübergangsdiagramm|Graphen]] bzw. eine [[Übergangstabelle|Automatentafel]] dargestellt werden.

{| class="wikitable" style="text-align:center;"
|+ Beschreibung eines Automaten
| [[Datei:MooreMachineExample.svg|220px]]
|
{| class="wikitable zebra" style="text-align:center"
|-
! <math>\delta</math> (Übergang)↘ !! &nbsp;&nbsp;<math>x</math>&nbsp;&nbsp; !! &nbsp;&nbsp;<math>y</math>&nbsp;&nbsp; !! &nbsp;&nbsp;<math>z</math>&nbsp;&nbsp; !! <math>\lambda</math> (Ausgabe)
|-
| '''q<sub>0</sub>''' || <math>q_3</math> || <math>q_3</math> || <math>q_1</math> || <math>b</math>
|-
| '''q<sub>1</sub>''' || <math>q_3</math> || <math>q_2</math> || <math>q_3</math> || <math>a</math>
|-
| '''q<sub>2</sub>''' || - || <math>q_3</math> || - || <math>a</math>
|-
| '''q<sub>3</sub>''' || <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 <math>x</math> oder das Zeichen <math>z</math> einliest, geht der Automat in den Zustand <math>q_3</math> über. Beim Erreichen des Zustandes <math>q_3</math> erfolgt die Ausgabe <math>c</math>.

== Medwedew-Automat ==
{{Hauptartikel|Medwedew-Automat}}
[[Datei:Medwedew-Automat.png|mini|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 Sprache|Russische]] einen eigenen Artikel anhängte.

=== Vorteile ===
* Die Ausgabe ist schneller.
* Die [[Taktflanke]] der [[Flipflop|Flipflops]] kann kleiner gestellt werden.

== Überführung in einen Mealy-Automaten ==
Die [[Ausgabe (Computer)|Ausgabe]] eines [[Mealy-Automat]]en ist von seinem Zustand und seiner [[Eingabe (Computer)|Eingabe]] abhängig.
Jeder Moore-Automat lässt sich sehr leicht in einen äquivalenten [[Mealy-Automat|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:

[[Datei:Moore to Mealy.png]]

== Siehe auch ==
* [[Automatentheorie]]
* [[Mealy-Automat]]
* [[Medwedew-Automat]]
* [[Deterministischer endlicher Automat]]
* [[Nichtdeterministischer endlicher Automat]]

== Literatur ==
* {{Literatur |Autor=Gottfried Vossen, Kurt-Ulrich Witt |Titel=Grundkurs theoretische Informatik |TitelErg=Eine anwendungsbezogene Einführung |Hrsg= |Sammelwerk= |Band= |Nummer= |Auflage= |Verlag=Vieweg+Teubner |Ort=Wiesbaden |Datum=2011 |Seiten= |ISBN=978-3-8348-1537-8 |Online={{Google Buch|BuchID=Zo7I8kutRVIC|Seite=121}}}}


[[Kategorie:Automatentheorie]]