Wikipedia · einfach zusammengefasst · Stand
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 …
Inhalt4 Abschnitte
Grundidee
Ein Moore-Automat ist ein endlicher Automat, bei dem die Ausgabe ausschließlich vom aktuellen Zustand abhängt. Sobald ein Zustand erreicht wird, erzeugt der Automat dessen fest zugeordnete Ausgabe; der Übergang, über den der Zustand erreicht wurde, spielt dafür keine Rolle. Moore-Automaten können deterministisch oder nichtdeterministisch sein.
Damit unterscheiden sie sich vom Mealy-Automaten: Bei einem Mealy-Automaten hängt die Ausgabe sowohl vom Zustand als auch von der Eingabe ab. Die Anzahl der Zustände eines Moore-Automaten ist nicht kleiner als die Anzahl der Zustände des entsprechenden Mealy-Automaten.
Formaler Aufbau
Ein Moore-Automat wird als 7-Tupel \mathcal{A}=(Q,\Sigma,\Omega,\delta,\lambda,q_0,F) definiert:
- Q ist die endliche Zustandsmenge, also |Q|<\infty.
- \Sigma ist das endliche Eingabealphabet, |\Sigma|<\infty.
- \Omega ist das endliche Ausgabealphabet, |\Omega|<\infty.
- \delta:Q\times\Sigma\rightarrow Q ist die Übergangsfunktion. Sie legt fest, in welchen Zustand der Automat nach einer Eingabe wechselt.
- \lambda:Q\rightarrow\Omega ist die Ausgabefunktion. Sie ordnet jedem Zustand ein Ausgabesymbol zu.
- q_0\in Q ist der Startzustand.
- F\subseteq Q ist die endliche Menge akzeptierender Zustände.
Liest der Automat ein Eingabewort J\in\Sigma^* und hält danach in einem Zustand aus F, gehört J zur Sprache L(A). Ist die vom Automaten akzeptierte reguläre Sprache nicht von Interesse, kann F weggelassen werden; dann wird der Automat als 6-Tupel definiert.
Zustände, Übergänge und Ausgaben
Ein deterministisches Beispiel ist durch das 6-Tupel (Q,\Sigma,\Omega,\delta,\lambda,q_0) gegeben, mit Q=\{q_0,q_1,q_2,q_3\}, \Sigma=\{x,y,z\}, \Omega=\{a,b,c\} und Startzustand q_0. Übergangsfunktion und Ausgabefunktion können in einem Graphen oder einer Automatentafel dargestellt werden.
Die Tabelle des Beispiels ordnet den Zuständen die Ausgaben \lambda(q_0)=b, \lambda(q_1)=a, \lambda(q_2)=a und \lambda(q_3)=c zu. Beispielsweise führen vom Zustand q_1 sowohl die Eingabe x als auch z nach q_3. Beim Erreichen von q_3 wird deshalb c ausgegeben. Nicht für jede Zustands-Eingabe-Kombination ist im Beispiel ein Übergang angegeben.
In der Digitaltechnik lässt sich ein Moore-Automat mit zwei Schaltnetzen und einem getakteten Speicherblock realisieren. Die Logik kann auf einer Leiterplatte verdrahtet oder mit programmierbarer Logik und einer Hardwarebeschreibungssprache umgesetzt werden. Für Logikschaltkreise werden Eingabe-, Zustands- und Ausgabealphabet in Binärcode umgewandelt, etwa Eingaben x,y, Zustände q_0,q_1 und Ausgaben a,b in Bitfolgen.
Sonderform und Umwandlung
Ein Medwedew-Automat ist eine Sonderform des Moore-Automaten. Bei ihm bilden die Zustände unmittelbar die Ausgabe; ein Ausgangsnetzwerk ist daher nicht vorhanden. Jeder Medwedew-Automat ist ein Moore-Automat, aber nicht jeder Moore-Automat ein Medwedew-Automat.
Als Vorteile werden genannt: Die Ausgabe ist schneller, und die Taktflanke der Flipflops kann kleiner eingestellt werden.
Jeder Moore-Automat kann in einen äquivalenten Mealy-Automaten überführt werden. Dazu wird das Ausgabesymbol des Eingangszustands auf die jeweilige Transition, also den Zustandsübergang, geschrieben. Dadurch wird die beim Moore-Automaten zustandsgebundene Ausgabe im Mealy-Automaten an den Übergängen dargestellt.
