Moore-Maschine - Moore machine

In der Rechentheorie ist ein Moore-Automat ein endlicher Automat, dessen Ausgabewerte nur durch seinen aktuellen Zustand bestimmt werden . Dies steht im Gegensatz zu einer Mealy-Maschine , deren Ausgabewerte sowohl durch ihren aktuellen Zustand als auch durch die Werte ihrer Eingaben bestimmt werden. Die Moore-Maschine ist nach Edward F. Moore benannt , der das Konzept 1956 in einem Artikel „ Gedanken-Experimente on Sequential Machines“ vorstellte .

Formale Definition

Eine Moore-Maschine kann als 6-Tupel definiert werden, das aus Folgendem besteht:

  • Eine endliche Menge von Zuständen
  • Ein Startzustand (auch Startzustand genannt), der ein Element von ist
  • Eine endliche Menge der Eingang genannt Alphabet
  • Eine endliche Menge der Ausgang genannt Alphabet
  • Eine Übergangsfunktion , die einen Zustand und das Eingabealphabet auf den nächsten Zustand abbildet
  • Eine Ausgabefunktion, die jeden Zustand dem Ausgabealphabet zuordnet

Eine Moore-Maschine kann als eingeschränkter Typ eines endlichen Wandlers betrachtet werden .

Visuelle Darstellung

Tabelle

Die Zustandsübergangstabelle ist eine Tabelle, die die Beziehung zwischen einer Eingabe und einem Zustand zeigt.

Diagramm

Das Zustandsdiagramm für eine Moore-Maschine oder ein Moore-Diagramm ist ein Diagramm, das jedem Zustand einen Ausgabewert zuordnet. Die Moore-Maschine ist ein Output-Produzent.

Beziehung zu Mealy-Maschinen

Da Moore- und Mealy-Maschinen beide Arten von endlichen Automaten sind, sind sie gleichermaßen ausdrucksstark: Jeder Typ kann zum Parsen einer regulären Sprache verwendet werden .

Der Unterschied zwischen Moore-Maschinen und Mealy-Maschinen besteht darin, dass bei letzteren die Ausgabe eines Übergangs durch die Kombination des aktuellen Zustands und der aktuellen Eingabe ( als Eingabe zu ) bestimmt wird, im Gegensatz zu nur dem aktuellen Zustand ( als Eingabe zu ). . Als Zustandsdiagramm dargestellt ,

  • für eine Moore-Maschine ist jeder Knoten (Zustand) mit einem Ausgabewert gekennzeichnet;
  • bei einer Mealy-Maschine ist jeder Bogen (Übergang) mit einem Ausgabewert gekennzeichnet.

Jeder Moore - Maschine entspricht die Mealy - Maschine mit den gleichen Zuständen und Übergängen und der Ausgangsfunktion , die jedes Zustand-Eingangspaar nimmt und die Ausbeuten , in denen ist ‚s Ausgabefunktion und ist ‘ s Übergangsfunktion.

Allerdings kann nicht jede Mealy-Maschine in eine gleichwertige Moore-Maschine umgewandelt werden. Einige können nur in eine fast äquivalente Moore-Maschine umgewandelt werden, deren Ausgaben zeitlich verschoben sind. Dies liegt an der Art und Weise, wie Zustandslabels mit Übergangslabels gepaart werden, um die Eingabe/Ausgabe-Paare zu bilden. Betrachten Sie einen Übergang von Staat zu Staat . Die Eingabe, die den Übergang verursacht, beschriftet die Kante . Die Ausgabe, die dieser Eingabe entspricht, ist das Label von state . Beachten Sie, dass dies der Quellzustand des Übergangs ist. Für jede Eingabe ist die Ausgabe also bereits vor dem Empfang der Eingabe festgelegt und hängt allein vom aktuellen Zustand ab. Dies ist die ursprüngliche Definition von E. Moore. Es ist ein häufiger Fehler, das Statuslabel als Ausgabe für den Übergang zu verwenden .

Beispiele

Typen nach Anzahl der Ein-/Ausgänge.

Einfach

Einfache Moore-Maschinen haben einen Eingang und einen Ausgang:

Die meisten digitalen elektronischen Systeme sind als getaktete sequentielle Systeme ausgelegt . Taktgesteuerte sequentielle Systeme sind eine eingeschränkte Form der Moore-Maschine, bei der sich der Zustand nur ändert, wenn sich das globale Taktsignal ändert. Typischerweise wird der aktuelle Zustand in Flip-Flops gespeichert , und ein globales Taktsignal wird mit dem "Takt"-Eingang der Flip-Flops verbunden. Getaktete sequentielle Systeme sind eine Möglichkeit, Metastabilitätsprobleme zu lösen. Eine typische elektronische Moore-Maschine enthält eine kombinatorische Logikkette , um den aktuellen Zustand in die Ausgänge (Lambda) zu decodieren. In dem Moment, in dem sich der aktuelle Status ändert, breiten sich diese Änderungen durch diese Kette aus, und fast augenblicklich wird die Ausgabe aktualisiert. Es gibt Konstruktionstechniken, um sicherzustellen, dass während dieser kurzen Zeit keine Störungen an den Ausgängen auftreten, während sich diese Änderungen durch die Kette ziehen, aber die meisten Systeme sind so konzipiert, dass Störungen während dieser kurzen Übergangszeit ignoriert werden oder irrelevant sind. Die Ausgänge bleiben dann auf unbestimmte Zeit gleich ( LEDs bleiben hell, Strom bleibt mit den Motoren verbunden, Magnetspulen bleiben erregt usw.), bis die Moore-Maschine ihren Zustand wieder ändert.

Alt-Text

Ausgearbeitetes Beispiel

Ein sequentielles Netzwerk hat einen Eingang und einen Ausgang. Der Ausgang wird 1 und bleibt danach 1, wenn mindestens zwei Nullen und zwei Einsen als Eingänge aufgetreten sind.

Beispiel Moore Maschine
Beispiel Moore Maschine

Rechts ist eine Moore-Maschine mit neun Zuständen für die obige Beschreibung dargestellt. Der Anfangszustand ist Zustand A und der Endzustand ist Zustand I. Die Zustandstabelle für dieses Beispiel sieht wie folgt aus:

Aktuellen Zustand Eingang Nächstes Bundesland Ausgabe
EIN 0 D 0
1 B
B 0 E 0
1 C
C 0 F 0
1 C
D 0 G 0
1 E
E 0 H 0
1 F
F 0 ich 0
1 F
G 0 G 0
1 H
H 0 H 0
1 ich
ich 0 ich 1
1 ich

Komplex

Komplexere Moore-Maschinen können sowohl mehrere Eingänge als auch mehrere Ausgänge haben.

Gedankenexperimente

In Moores Papier " Gedankenexperimente zu sequentiellen Maschinen" werden die Automaten (oder Maschinen) als Zustände, Eingabesymbole und Ausgabesymbole definiert. Neun Sätze werden über die Struktur von und Experimente mit bewiesen . Später wurden „ Maschinen“ als „Moore-Maschinen“ bekannt.

Am Ende der Arbeit wird im Abschnitt "Weitere Probleme" folgende Aufgabenstellung genannt:

Ein weiteres direkt folgendes Problem ist die Verbesserung der Schranken in den Sätzen 8 und 9.

Der Satz von Moore 8 wird wie folgt formuliert:

Gegeben eine beliebige Maschine , so dass alle zwei ihrer Zustände voneinander unterscheidbar sind, dann existiert ein Experiment der Länge, das den Zustand am Ende des Experiments bestimmt.

1957 bewies AA Karatsuba die beiden folgenden Theoreme, die Moores Problem der Verbesserung der Grenzen der Experimentlänge seines "Theorem 8" vollständig lösten.

Theorem A. Wenn eine Maschine so ist, dass alle zwei ihrer Zustände voneinander unterscheidbar sind, dann existiert ein verzweigtes Experiment von maximaler Länge, durch das man den Zustand am Ende des Experiments bestimmen kann .

Satz B. Es gibt eine Maschine, von der alle zwei Zustände voneinander unterscheidbar sind, so dass die Länge der kürzesten Experimente, die den Zustand der Maschine am Ende des Experiments bestimmen, gleich ist .

Die Theoreme A und B wurden als Grundlage für die Studienarbeit eines Studenten des vierten Studienjahres, AA Karatsuba, "Zu einem Problem aus der Automatentheorie", verwendet, der sich beim Wettbewerb der Studentenarbeiten der Fakultät für durch Testimonial-Referenz auszeichnete Mechanik und Mathematik der Moskauer Lomonosow State University 1958. Der Aufsatz von Karatsuba wurde der Zeitschrift Uspekhi Mat. Nauk am 17. Dezember 1958 und wurde dort im Juni 1960 veröffentlicht.

Bis heute (2011) ist Karatsubas Ergebnis zur Versuchsdauer das einzige exakte nichtlineare Ergebnis sowohl in der Automatentheorie als auch in ähnlichen Problemen der Computational Complexity Theory.

Siehe auch

Verweise

Weiterlesen

  • Conway, JH (1971). Reguläre Algebra und endliche Maschinen . London: Chapman und Hall. ISBN 0-412-10620-5. Zbl  0231.94041 .
  • Moore EF Gedanken-Experimente an sequentiellen Maschinen. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956).
  • Karatsuba AA Lösung eines Problems aus der Theorie endlicher Automaten. Usp. Matte. Nauk, 15:3, 157–159 (1960).
  • Karatsuba AA Experimente mit Automaten (Deutsch) Elektron. Informationsverarb. Kybernetik, 11, 611-612 (1975).
  • Karatsuba AA Liste der Forschungsarbeiten .

Moore-and-Mealy-Maschine

Externe Links