Moore-Automat

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.

Inhaltsverzeichnis

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(\left| Q \right| < \infty\right).
  • Σ 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 Ausgabefunktion: \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. 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 \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 q0 = q0.

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

Beschreibung eines Automaten
MooreAutomaton.png
δ (Übergang)↘   x     y     z   λ (Ausgabe)
q0 q3 q3 q1 b
q1 q3 q2 q3 a
q2 - q3 - a
q3 q3 - q2 c
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 q1 befindet und von dort aus das Zeichen "x" oder das Zeichen "z" einliest, geht der Automat in den Zustand q3 über. Beim Erreichen des Zustandes q3 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:

Moore to Mealy.png

Literatur

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Moore Automat — Moore o automatas statusas T sritis automatika atitikmenys: angl. Moore automaton vok. Moore Automat, m rus. автомат Мура, m pranc. automate Moore, m ryšiai: sinonimas – Muro automatas …   Automatikos terminų žodynas

  • 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… …   Deutsch Wikipedia

  • Moore — ist der Plural von Moor und der Name mehrerer Personen: siehe Moore (Familienname) Fließgewässer: Moore River, Fluss in West Australien Moore (Leine), westlicher Zufluss der Leine Orte in den Vereinigten Staaten: Moore (Arkansas) Moore (Idaho)… …   Deutsch Wikipedia

  • Moore automaton — Moore o automatas statusas T sritis automatika atitikmenys: angl. Moore automaton vok. Moore Automat, m rus. автомат Мура, m pranc. automate Moore, m ryšiai: sinonimas – Muro automatas …   Automatikos terminų žodynas

  • Moore'o automatas — statusas T sritis automatika atitikmenys: angl. Moore automaton vok. Moore Automat, m rus. автомат Мура, m pranc. automate Moore, m ryšiai: sinonimas – Muro automatas …   Automatikos terminų žodynas

  • Moore-Nachbarschaft — Die Moore Nachbarschaft ist eine Nachbarschaftsbeziehung in einem quadratischen Raster. Alle Flächen, welche mindestens eine Ecke mit der Basisfläche gemeinsam haben, gelten als Nachbarn.[1] Sie wurde nach Edward F. Moore benannt und wird auch… …   Deutsch Wikipedia

  • Automat (Informatik) — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • automate Moore — Moore o automatas statusas T sritis automatika atitikmenys: angl. Moore automaton vok. Moore Automat, m rus. автомат Мура, m pranc. automate Moore, m ryšiai: sinonimas – Muro automatas …   Automatikos terminų žodynas

  • Mealy Automat — Ein Mealy Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore Automat) von seinem Zustand und seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird. Der… …   Deutsch Wikipedia

  • Mealy-Automat — Ein Mealy Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore Automaten) von seinem Zustand und seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird. Der …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”