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 definiert werden:
- ist eine endliche Menge von Zuständen .
- ist das Eingabealphabet. ,
- ist das Ausgabealphabet.
- ist die Übergangsfunktion
- definiert die Ausgabefunktion:
- ist der Startzustand.
- ist eine (endliche) Menge möglicher akzeptierender Zustände (= Endzustandsmenge). Wenn der Automat nach Lesen des Eingabewortes in einem Zustand aus hält, so gehört zur Sprache .
Wenn die reguläre Sprache des Automaten uninteressant ist, kann 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.
|
|
|
Beschreibung eines Automaten
Gegeben sei ein durch ein 6-Tupel definierter, deterministischer endlicher Automat mit
,
,
und .
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 im Zustand befindet und von dort aus das Zeichen "x" oder das Zeichen "z" einliest, geht der Automat in den Zustand über. Beim Erreichen des Zustandes 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
- Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Eine anwendungsbezogene Einführung. Vieweg+Teubner, 2011, ISBN 978-3-8348-1537-8 (eingeschränkte Vorschau in der Google-Buchsuche).