Finite-State-Maschine

Kurs von Automaten

(Klicken auf jede Ebene erhält einen Artikel zu diesem Thema)

A Finite-State-Maschine (FSM) oder Finite-State-Automaten (FSA, Plural: Automaten), Finite Automatonoder einfach ein Zustandsmaschine, ist eine mathematische Berechnungsmodell. Es ist ein abstrakte Maschine das kann genau in einer von einer begrenzten Anzahl von sein Zustände Zu jeder Zeit. Die FSM kann als Reaktion auf einige von einem Zustand zu einem anderen wechseln Eingänge; Die Änderung von einem Zustand zum anderen wird a genannt Überleitung.^[1] Ein FSM wird durch eine Liste seiner Zustände, ihren Ausgangszustand und die Eingänge definiert, die jeden Übergang auslösen. Finite-State-Maschinen sind zwei Arten-deterministische Finite-State-Maschinen und Nichtdeterministische Finite-State-Maschinen.^[2] Eine deterministische Finite-State-Maschine kann zu nicht deterministischen Konstruktion konstruiert werden.

Das Verhalten staatlicher Maschinen kann in vielen Geräten der modernen Gesellschaft beobachtet werden, die eine vorgegebene Folge von Aktionen ausführen, die von einer Abfolge von Ereignissen, mit denen sie präsentiert werden, abhängig sind. Einfache Beispiele sind Verkaufsautomaten, die Produkte ausgeben, wenn die richtige Kombination von Münzen abgelagert wird, Aufzüge, deren Abfolge von Stopps durch die von den Fahrern angeforderten Böden bestimmt wird, Ampeln, die die Sequenz ändern, wenn Autos warten, und Kombinationsschlösser, die die Eingabe einer Abfolge von Zahlen in der richtigen Reihenfolge erfordern.

Die Finite-State-Maschine hat weniger Rechenleistung als einige andere Berechnungsmodelle wie die Turing Maschine.^[3] Die Rechenleistung bedeutet, dass es Rechenaufgaben gibt, die eine Turing -Maschine erledigen kann, ein FSM jedoch nicht. Dies liegt daran, dass ein FSMs Erinnerung ist durch die Anzahl der Staaten begrenzt, die es hat. Eine Finite-State-Maschine hat die gleiche Rechenleistung wie a Turing Maschine Das ist eingeschränkt, so dass sein Kopf nur "Lese-" -Operationen ausführt und sich immer von links nach rechts bewegen muss. FSMs werden im allgemeineren Bereich von untersucht Automatenheorie.

Beispiel: münzbetriebener Drehkreuz

Zustandsdiagramm für eine Drehkreuze

Ein Drehkreuz

Ein Beispiel für einen einfachen Mechanismus, der von einer Zustandsmaschine modelliert werden kann, ist a Drehkreuz.^[4][5] Ein Drehkreuz, der den Zugang zu U -Bahnen und Vergnügungsparkfahrten steuert, ist ein Tor mit drei rotierenden Armen in der Taillenhöhe, einer über den Eingang. Zunächst sind die Arme verschlossen, blockieren den Eingang und verhindert, dass die Gäste durchgehen. Deposition einer Münze oder Zeichen In einem Schlitz auf dem Drehkreuz entsperren Sie die Arme, sodass ein einzelner Kunde durchdringen kann. Nachdem der Kunde durchlaufen wird, werden die Arme wieder verschlossen, bis eine andere Münze eingefügt wird.

Der Drehkreuz ist als Zustandsmaschine betrachtet und hat zwei mögliche Zustände: Gesperrt und Entsperrt.^[4] Es gibt zwei mögliche Eingaben, die sich auf ihren Zustand auswirken: eine Münze in den Steckplatz zu legen (Münze) und den Arm drücken (drücken). Im verschlossenen Zustand hat das Drücken des Arms keine Wirkung; Egal wie oft die Eingabe drücken wird gegeben, es bleibt im verschlossenen Zustand. Eine Münze eingeben - das heißt, der Maschine a zu geben a Münze Eingabe - verschiebt den Zustand von Gesperrt zu Entsperrt. Im freigeschalteten Zustand hat das Einfügen zusätzlicher Münzen keine Wirkung. das heißt, zusätzliche geben Münze Eingaben ändert den Zustand nicht. Ein Kunde drückt jedoch durch die Arme und gibt a drücken Eingabe, verlagert den Zustand wieder auf Gesperrt.

Die Drehstaat Maschine kann durch a dargestellt werden Staatstabelle, zeigt für jeden möglichen Zustand die Übergänge zwischen ihnen (basierend auf den Eingängen der Maschine) und den Ausgängen, die sich aus jedem Eingang ergeben:

Aktuellen Zustand	Eingang	Nächster Staat	Ausgabe
Gesperrt	Münze	Entsperrt	Schaltet die Drehkreuze frei, damit der Kunde durchdringen kann.
	drücken	Gesperrt	Keiner
Entsperrt	Münze	Entsperrt	Keiner
	drücken	Gesperrt	Wenn der Kunde durchgeschoben hat, sperrt die Drehkreuze.

Die Drehstaat Maschine kann auch durch a dargestellt werden gerichteter Graph genannt Zustandsdiagramm (Oben). Jeder Staat wird durch a dargestellt Knoten (Kreis). Kanten (RänderPfeile) Zeigen Sie die Übergänge von einem Zustand zum anderen. Jeder Pfeil ist mit dem Eingang gekennzeichnet, der diesen Übergang auslöst. Eine Eingabe, die keine Zustandsänderung verursacht (wie z. Münze Eingabe in die Entsperrt Zustand) wird durch einen kreisförmigen Pfeil dargestellt, der in den ursprünglichen Zustand zurückkehrt. Der Pfeil in die Gesperrt Der Knoten aus dem schwarzen Punkt zeigt an, dass es sich um den Anfangszustand handelt.

Konzepte und Terminologie

A Zustand ist eine Beschreibung des Status eines Systems, das darauf wartet, a zu führen Überleitung. Ein Übergang ist eine Reihe von Aktionen, die ausgeführt werden müssen, wenn eine Bedingung erfüllt ist oder wenn ein Ereignis empfangen wird. Wenn Sie beispielsweise ein Audiosystem verwenden, um das Radio anzuhören (das System befindet sich im Status "Radio"), führt der Empfang eines "nächsten" Stimulus zum nächsten Sender. Wenn sich das System im Status "CD" befindet, führt der "nächste" Stimulus zum nächsten Track. Identische Reize auslösen unterschiedliche Aktionen in Abhängigkeit vom aktuellen Zustand.

In einigen Darstellungen von Finite-State-Maschinen ist es auch möglich, Aktionen mit einem Zustand zu assoziieren:

• Eine Eintragsaktion: ausgeführt beim Betreten der Staat und
• Eine Ausstiegsaktion: durchgeführt Beim Verlassen der Staat.

Darstellungen

Abb. 1 Uml -Status -Diagrammbeispiel (ein Toaster -Ofen)

Abb. 2 SDL -Statusmaschinenbeispiel

Abb. 3 Beispiel einer einfachen Finite-State-Maschine

Status-/Ereignisetabelle

Mehrere Staatstabelle Typen werden verwendet. Die häufigste Darstellung ist unten dargestellt: Die Kombination aus Stromzustand (z. B. b) und Eingabe (z. B. y) zeigt den nächsten Zustand (z. B. c). Die Informationen der vollständigen Aktion werden in der Tabelle nicht direkt beschrieben und können nur mit Fußnoten hinzugefügt werden.^{[Weitere Erklärung erforderlich]} Eine FSM Staatstabellen (siehe auch Virtuelle Finite-State-Maschine).

UML -Staatsmaschinen

Das Einheitliche Modellierungssprache hat eine Notation zur Beschreibung von Staatsmaschinen. UML -Staatsmaschinen Überwinden Sie die Einschränkungen traditioneller Finite-State-Maschinen und behalten gleichzeitig ihre Hauptvorteile bei. UML State -Maschinen stellen die neuen Konzepte von vor Hierarchisch verschachtelte Staaten und orthogonale Regionen, während der Begriff von Aktionen. UML -Staatsmaschinen haben die Eigenschaften beider Mehlige Maschinen und Moore -Maschinen. Sie unterstützen Aktionen das hängt sowohl vom Status des Systems als auch vom Auslösen ab Veranstaltungwie in mehligen Maschinen sowie Eintritts- und Ausgangsaktionen, die eher mit Zuständen als mit Übergängen verbunden sind, wie in Moore -Maschinen.

SDL -Staatsmaschinen

Das Spezifikation und Beschreibung Sprache ist ein Standard von Itu Dies beinhaltet grafische Symbole, um Aktionen im Übergang zu beschreiben:

• Senden Sie eine Veranstaltung
• Erhalten Sie eine Veranstaltung
• Starten Sie einen Timer
• einen Timer abbrechen
• Starten Sie eine andere gleichzeitige Zustandsmaschine
• Entscheidung

SDL bettet grundlegende Datentypen ein, die als "abstrakte Datentypen", eine Aktionssprache und eine Ausführungssemantik bezeichnet werden, um die endliche Zustandsmaschine ausführbar zu machen.

Andere Staatsdiagramme

Es gibt eine große Anzahl von Varianten, die einen FSM darstellen, wie in Abbildung 3.

Verwendungszweck

Zusätzlich zu ihrer Verwendung in den hier vorgestellten Modellierung von reaktiven Systemen sind Finite-State-Maschinen in vielen verschiedenen Bereichen signifikant, einschließlich Elektrotechnik, Linguistik, Informatik, Philosophie, Biologie, Mathematik, Videospielprogrammierung, und Logik. Finite-State-Maschinen sind eine Klasse von Automata, die in untersucht werden Automatenheorie und die Theorie der Berechnung. In der Informatik werden Finite-State-Maschinen häufig zur Modellierung des Anwendungsverhaltens verwendet (Kontrolltheorie), Design von Hardware -digitale Systeme, Softwareentwicklung, Compiler, Netzwerkprotokolle, und Computerlinguistik.

Einstufung

Finite-State-Maschinen können in Akzeptoren, Klassifizierer, Wandler und Sequenzer unterteilt werden.^[6]

Akzeptoren

Abb. 4: Akzeptor FSM: Analyse der Zeichenfolge "nett".

Abb. 5: Darstellung eines Akzeptors; Dieses Beispiel zeigt eines, das bestimmt, ob eine Binärzahl eine gleichmäßige Anzahl von 0s hat, wo S₁ ist ein Staat akzeptieren und S₂ ist ein Nicht akzeptierender Zustand.

Akzeptoren (auch genannt Detektoren oder Erkenner) Binärausgabe erzeugen und angeben, ob die empfangene Eingabe akzeptiert wird oder nicht. Jeder Zustand eines Akzeptors ist entweder Akzeptieren oder nicht akzeptierend. Sobald alle Eingaben eingegangen sind, wird der Eingang akzeptiert, wenn der aktuelle Zustand ein akzeptierender Zustand ist. Ansonsten wird es abgelehnt. In der Regel ist die Eingabe a Sequenz von Symbolen (Figuren); Aktionen werden nicht verwendet. Der Startzustand kann auch ein akzeptierender Zustand sein. In diesem Fall akzeptiert der Akzeptor die leere Zeichenfolge. Das Beispiel in Abbildung 4 zeigt einen Akzeptor, der die Zeichenfolge "nett" akzeptiert. In diesem Akzeptor ist der einzige akzeptierende Staat Bundesstaat 7.

A (möglicherweise unendlich) Satz von Symbolsequenzen, als a genannt formelle Sprache, ist ein Regelmäßige Sprache Wenn es einen Akzeptor gibt, der akzeptiert exakt das Set. Zum Beispiel ist der Satz von binären Zeichenfolgen mit einer geraden Anzahl von Nullen eine reguläre Sprache (vgl. Abb. 5), während der Satz aller Zeichenfolgen, deren Länge eine Primzahl ist, nicht ist.^{[7]: 18, 71}

Ein Akzeptor könnte auch als Definieren einer Sprache beschrieben werden, die jede vom Akzeptor akzeptierte Zeichenfolge enthält, aber keine der abgelehnte; Diese Sprache ist akzeptiert durch den Akzeptor. Per Definition sind die von Akzeptoren akzeptierten Sprachen die reguläre Sprachen.

Das Problem der Bestimmung der von einem bestimmten Akzeptor akzeptierten Sprache ist eine Instanz der Algebraischer Pfadproblem- Ich selbst eine Verallgemeinerung der kürzestes Pfadproblem an Grafiken mit Kanten, die durch die Elemente eines (willkürlichen) gewichtet wurden Seming.^{[8][9][Jargon]}

Ein Beispiel für einen akzeptierenden Zustand erscheint in Abb. 5: a Deterministische endliche Automaten (DFA), das erkennt, ob die binär Eingabezeichenfolge enthält eine gleichmäßige Anzahl von 0s.

S₁ (Dies ist auch der Startzustand) zeigt den Zustand an, in dem eine gleichmäßige Anzahl von 0s eingegeben wurde. S₁ ist daher ein akzeptierender Zustand. Dieser Akzeptor wird in einem Akzeptanzstaat fertiggestellt, wenn die binäre Zeichenfolge eine gleichmäßige Anzahl von 0s enthält (einschließlich einer binären Zeichenfolge, die Nr. 0s enthält). Beispiele für Strings, die von diesem Akzeptor akzeptiert werden, sind ε (das leerer String), 1, 11, 11 ..., 00, 010, 1010, 10110 usw.

Klassifikatoren

Klassifikatoren sind eine Verallgemeinerung von Akzeptoren, die produzieren n-ary Ausgang wo n ist streng größer als zwei.^[10]

Wandler

Abb. 6 Transducer FSM: Beispiel für Moore -Modell

Abb. 7 Transducer FSM: Beispiel für Mealy -Modell

Wandler Erstellen Sie die Ausgabe basierend auf einem bestimmten Eingang und/oder einem Zustand unter Verwendung von Aktionen. Sie werden für Kontrollanwendungen und im Bereich von verwendet Computerlinguistik.

In Kontrollanwendungen werden zwei Typen unterschieden:

Moore -Maschine

Das FSM verwendet nur Einstiegsaktionen, d. H. Die Ausgabe hängt nur vom Zustand ab. Der Vorteil des Moore -Modells ist eine Vereinfachung des Verhaltens. Betrachten Sie eine Aufzugstür. Die Statusmaschine erkennt zwei Befehle: "command_open" und "command_close", die sich ändern. Die Eingangsaktion (E :) In State "Öffnung" beginnt einen Motor, der die Tür öffnet, und die Eingangsaktion im Zustand "Schließung" startet einen Motor in die andere Richtung, die die Tür schließt. Staaten "geöffnet" und "geschlossen" stoppen den Motor, wenn sie vollständig geöffnet oder geschlossen werden. Sie signalisieren der Außenwelt (z. B. anderen Staatsmaschinen) die Situation: "Tür ist offen" oder "Tür ist geschlossen".

Mehlige Maschine

Das FSM verwendet auch Eingabeaktionen, d. H. Die Ausgabe hängt von Eingabe und Zustand ab. Die Verwendung eines mehligen FSM führt häufig zu einer Verringerung der Anzahl der Zustände. Das Beispiel in Abbildung 7 zeigt eine mehlige FSM, die das gleiche Verhalten wie im Moore -Beispiel implementiert (das Verhalten hängt von dem implementierten FSM -Ausführungsmodell ab und funktioniert z. B. für Virtuelle FSM aber nicht für ereignisgesteuerte FSM). Es gibt zwei Eingabeaktionen (ich: "Starten Sie den Motor, um die Tür zu schließen, wenn command_close eintrifft" und "Motor in die andere Richtung starten, um die Tür zu öffnen, wenn command_open eintrifft". Die "Öffnen" und "Schließen" Zwischenzustände sind nicht gezeigt.

Sequenzer

Sequenzer (auch genannt Generatoren) sind eine Unterklasse von Akzeptoren und Wandlern, die ein Eingangs-Alphabet mit einem Buchstaben haben. Sie erzeugen nur eine Sequenz, die als Ausgangssequenz von Akzeptor- oder Wandlerausgängen gesehen werden kann.^[6]

Determinismus

Eine weitere Unterscheidung ist dazwischen deterministisch (DFA) und nicht deterministisch (NFA, GNFA) Automaten. In einem deterministischen Automat hat jeder Zustand genau einen Übergang für jede mögliche Eingabe. In einem nicht deterministischen Automaten kann ein Eingang zu einem, mehr als einem oder keinen Übergang für einen bestimmten Zustand führen. Das Poweret -Konstruktion Der Algorithmus kann jeden nichtterministischen Automat in einen (normalerweise komplexeren) deterministischen Automaten mit identischer Funktionalität umwandeln.

Eine Finite-State-Maschine mit nur einem Zustand wird als "kombinatorische FSM" bezeichnet. Es erlaubt nur Aktionen beim Übergang hinein ein Staat. Dieses Konzept ist nützlich in Fällen, in denen eine Reihe von Finite-State-Maschinen zusammenarbeiten müssen, und wenn es zweckmäßig ist, einen rein kombinatorischen Teil als eine Form von FSM für die Entwurfstools zu berücksichtigen.^[11]

Alternative Semantik

Es stehen andere Semantiksätze zur Verfügung, um Staatsmaschinen darzustellen. Beispielsweise gibt es Werkzeuge zum Modellieren und Entwerfen von Logik für eingebettete Controller.^[12] Sie kombinieren Hierarchische Staatsmaschinen (die normalerweise mehr als einen Stromzustand haben), Flussdiagramme und Wahrheitstabellen in eine Sprache, was zu einem anderen Formalismus und einer Reihe von Semantik führt.^[13] Diese Diagramme wie Harels ursprüngliche Staatsmaschinen,^[14] Unterstützen Sie hierarchisch verschachtelte Staaten, orthogonale Regionen, staatliche Maßnahmen und Übergangsaktionen.^[15]

Mathematisches Modell

In Übereinstimmung mit der allgemeinen Klassifizierung werden die folgenden formalen Definitionen gefunden.

A deterministische Finite-State-Maschine oder Deterministischer endlicher Staatakzeptor ist ein verfünffachen ${\ displayStyle (\ sigma, s, s_ {0}, \ delta, f)}$, wo:

• ${\ displayStyle \ sigma}$ ist der Eingang Alphabet (eine endliche nicht leere Symbole);
• ${\ displayStyle S}$ ist eine endliche, nicht leere Zustände;
• ${\ displayStyle s_ {0}}$ ist ein Anfangszustand, ein Element von ${\ displayStyle S}$;
• ${\ displayStyle \ Delta}$ ist die staatliche Übergangsfunktion: ${\ displayStyle \ Delta: S \ Times \ sigma \ rightarrow s}$ (in einem Nichtdeterministisches endliches Automaten es wäre ${\ displaystyle \ delta: s \ times \ sigma \ rightarrow {\ mathcal {p}} (s)}$, d.h. ${\ displayStyle \ Delta}$ würde eine Reihe von Zuständen zurückgeben);
• ${\ displayStyle f}$ ist die Menge der endgültigen Zustände, eine (möglicherweise leere) Teilmenge von ${\ displayStyle S}$.

Für deterministische und nicht deterministische FSMs ist es konventionell zuzulassen ${\ displayStyle \ Delta}$ ein ... zu sein Teilfunktion, d.h. ${\ displayStyle \ Delta (s, x)}$ muss nicht für jede Kombination von definiert werden ${\ displayStyle s \ in s}$ und ${\ displayStyle x \ in \ sigma}$. Wenn ein FSM ${\ displayStyle m}$ ist in einem Zustand ${\ displayStyle S}$Das nächste Symbol ist ${\ displayStyle x}$ und ${\ displayStyle \ Delta (s, x)}$ wird dann nicht definiert ${\ displayStyle m}$ kann einen Fehler ankündigen (d. H. Die Eingabe ablehnen). Dies ist nützlich für Definitionen allgemeiner Zustandsmaschinen, aber weniger nützlich, wenn Sie die Maschine transformieren. Einige Algorithmen in ihrem Standardformular erfordern möglicherweise Gesamtfunktionen.

Eine Finite-State-Maschine hat die gleiche Rechenleistung wie a Turing Maschine Das ist eingeschränkt, so dass sein Kopf nur "Lese-" -Operationen ausführt und sich immer von links nach rechts bewegen muss. Das heißt, jede formale Sprache, die von einer Finite-State-Maschine akzeptiert wird, wird von einer solchen Art von eingeschränkten Turing-Maschine akzeptiert und umgekehrt.^[16]

A Finite-State-Wandler ist ein Sextuple ${\ displayStyle (\ sigma, \ gamma, s, s_ {0}, \ delta, \ omega)}$, wo:

• ${\ displayStyle \ sigma}$ ist der Eingang Alphabet (eine endliche nicht leere Symbole);
• ${\ displayStyle \ gamma}$ ist das Ausgangsalphabet (ein endlicher nicht leerer Symbole);
• ${\ displayStyle S}$ ist eine endliche, nicht leere Zustände;
• ${\ displayStyle s_ {0}}$ ist der Anfangszustand, ein Element von ${\ displayStyle S}$;
• ${\ displayStyle \ Delta}$ ist die staatliche Übergangsfunktion: ${\ displayStyle \ Delta: S \ Times \ sigma \ rightarrow s}$;
• ${\ displayStyle \ Omega}$ ist die Ausgangsfunktion.

Wenn die Ausgangsfunktion vom Status und Eingangssymbol abhängt (${\ displayStyle \ Omega: S \ Times \ sigma \ rightarrow \ gamma}$) Diese Definition entspricht dem Mealy Model, und kann als modelliert werden Mehlige Maschine. Wenn die Ausgangsfunktion nur vom Zustand abhängt (${\ displayStyle \ Omega: s \ rightarrow \ gamma}$) Diese Definition entspricht dem Moore -Modell, und kann als modelliert werden Moore -Maschine. Eine Finite-State-Maschine ohne Ausgangsfunktion ist überhaupt als als bekannt Semiautomaton oder Übergangssystem.

Wenn wir das erste Ausgangssymbol einer Moore -Maschine ignorieren, ${\ displayStyle \ Omega (s_ {0})}$und dann kann es leicht in eine Ausgangsäquivalent-mehlige Maschine umgewandelt werden, indem die Ausgangsfunktion jedes mehligen Übergangs (d. H. Bezeichnung jeder Kante) mit dem Ausgangsymbol des Ziels Moore-Zustand festgelegt wird. Die Converse -Transformation ist weniger einfach, da ein mehliger Maschinenzustand möglicherweise unterschiedliche Ausgangsbezeichnungen für seine eingehenden Übergänge (Kanten) aufweist. Jeder solche Zustand muss in mehreren Moore -Maschinenzuständen aufgeteilt werden, eines für jedes Ausgangssymbol des Vorfalls.^[17]

Optimierung

Optimierung eines FSM bedeutet, eine Maschine mit der minimalen Anzahl von Zuständen zu finden, die dieselbe Funktion ausführen. Der am schnellsten bekannte Algorithmus ist der Hopcroft -Minimierungsalgorithmus.^[18][19] Andere Techniken sind die Verwendung eines Implikationstabelle, oder das Moore -Reduktionsverfahren.^[20] Zusätzlich können acyclische FSAs in minimiert werden lineare Zeit.^[21]

Implementierung

Hardwareanwendungen

Abb. 9 Die Schaltplan für einen 4-Bit Ttl Zähler, eine Art Zustandsmaschine

In einem Digitaler SchaltungEin FSM kann mit a gebaut werden Programmierbares Logikgerät, a Programmierbare Steuerung, Logik -Tore und Flip Flops oder Relais. Insbesondere erfordert eine Hardware -Implementierung a registrieren Zustandsvariablen speichern, einen Block von Kombinationslogik Dies bestimmt den Zustandsübergang und einen zweiten Block der Kombinationslogik, der die Ausgabe eines FSM bestimmt. Eine der klassischen Hardware -Implementierungen ist die Richards Controller.

In einem Medwedev -MaschineDie Ausgabe ist direkt mit dem Zustand Flip-Flops verbunden und minimiert die Zeitverzögerung zwischen Flip-Flops und Ausgang.^[22][23]

Durch Zustandscodierung für niedrige Leistung Zustandsmaschinen können optimiert werden, um den Stromverbrauch zu minimieren.

Softwareanwendungen

Die folgenden Konzepte werden häufig zum Erstellen von Softwareanwendungen mit Finite-State-Maschinen verwendet:

• Automata-basierte Programmierung
• Ereignisgesteuerte Finite-State-Maschine
• Virtuelle Finite-State-Maschine
• Zustandsdesignmuster

Finite-State-Maschinen und Compiler

Finite Automaten werden häufig in der verwendet Frontend von Programmiersprachen Compilern. Ein solches Frontend kann mehrere Finite-State-Maschinen umfassen, die a implementieren Lexikalanalysator und ein Parser. Ausgehend von einer Abfolge von Zeichen baut der lexikalische Analysator eine Abfolge von Sprach -Token (wie reservierte Wörter, Literale und Kennungen) auf, aus denen der Parser einen Syntaxbaum erstellt. Der lexikalische Analysator und der Parser verarbeiten den regulären und kontextfrei Teile der Grammatik der Programmiersprache.^[24]

Siehe auch

Verweise

Weitere Lektüre

Allgemein

• Sakarovitch, Jacques (2009). Elemente der Automata -Theorie. Übersetzt aus den Franzosen von Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Wagner, F., "Modellierungssoftware mit endlichen Staatsmaschinen: Ein praktischer Ansatz", Auerbach Publications, 2006, ISBN0-8493-8086-3.
• Itu-t, Empfehlung Z.100 Spezifikation und Beschreibung Sprache (SDL)
• Samek, M., Praktische staatsecharter in C/C ++, CMP Books, 2002, ISBN1-57820-110-1.
• Samek, M., Praktische UML staatsecharts in C/C ++, 2. Auflage, Newnes, 2008, ISBN0-7506-8706-1.
• Gardner, T., Advanced State Management, 2007
• Cassandras, C., LaFortune, S., "Einführung in diskrete Ereignissysteme". Kluwer, 1999, ISBN0-7923-8609-4.
• Timothy Kam, Synthese von endlichen Zustandsmaschinen: Funktionale Optimierung. Kluwer Academic Publishers, Boston 1997, ISBN0-7923-9842-4
• Tiziano Villa, Synthese von endlichen Zustandsmaschinen: Logikoptimierung. Kluwer Academic Publishers, Boston 1997, ISBN0-7923-9892-0
• Carroll, J., Long, D.,, Theorie der endlichen Automaten mit einer Einführung in formale Sprachen. Prentice Hall, Englewood Cliffs, 1989.
• Kohavi, Z.,, Wechsel und endliche Automatentheorie. McGraw-Hill, 1978.
• Gill, A., Einführung in die Theorie von Finite-State-Maschinen. McGraw-Hill, 1962.
• Ginsburg, S.,, Eine Einführung in die Theorie der mathematischen Maschine. Addison-Wesley, 1962.

Finite-State-Maschinen (Automatenheorie) in der theoretischen Informatik

• Arbib, Michael A. (1969). Theorien der abstrakten Automaten (1. Aufl.). Englewood Cliffs, N.J.: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
• Bobrow, Leonard S.; Arbib, Michael A. (1974). Diskrete Mathematik: Angewandte Algebra für Computer- und Informationswissenschaft (1. Aufl.). Philadelphia: W. B. Saunders Company, Inc. ISBN 978-0-7216-1768-8.
• Booth, Taylor L. (1967). Sequentielle Maschinen und Automatentheorie (1. Aufl.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Nummer 67-25924.
• Boolos, George; Jeffrey, Richard (1999) [1989]. Berechnbarkeit und Logik (3. Aufl.). Cambridge, England: Cambridge University Press. ISBN 978-0-521-20402-6.
• Brookshear, J. Glenn (1989). Berechnungstheorie: formale Sprachen, Automaten und Komplexität. Redwood City, Kalifornien: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
• Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Berechnbarkeit, Komplexität, Sprachen und Logik: Grundlagen der theoretischen Informatik (2. Aufl.). San Diego: Akademische Presse, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
• Hopcroft, John; Ullman, Jeffrey (1979). Einführung in die Automatentheorie, Sprachen und Berechnung (1. Aufl.). Masse lesen: Addison-Wesley. ISBN 978-0-201-02988-8.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Einführung in die Automatentheorie, Sprachen und Berechnung (2. Aufl.). Masse lesen: Addison-Wesley. ISBN 978-0-201-44124-6.
• Hopkin, David; Moss, Barbara (1976). Automaten. New York: Elsevier North-Holland. ISBN 978-0-444-00249-5.
• Kozen, Dexter C. (1997). Automaten und Berechnbarkeit (1. Aufl.). New York: Springer-Verlag. ISBN 978-0-387-94907-9.
• Lewis, Harry R.; Papadimitriou, Christos H. (1998). Elemente der Berechnungstheorie (2. Aufl.). Upper Saddle River, New Jersey: Prentice-Hall. ISBN 978-0-13-262478-7.
• Linz, Peter (2006). Formelle Sprachen und Automaten (4. Aufl.). Sudbury, MA: Jones und Bartlett. ISBN 978-0-7637-3798-6.
• Minsky, Marvin (1967). Berechnung: endliche und unendliche Maschinen (1. Aufl.). New Jersey: Prentice-Hall.
• Papadimitriou, Christos (1993). Rechenkomplexität (1. Aufl.). Addison Wesley. ISBN 978-0-201-53082-7.
• Penpfenger, Nicholas (1997). Theorien der Berechnung (1. Aufl.). Cambridge, England: Cambridge University Press. ISBN 978-0-521-55380-3.
• Rodger, Susan; Finley, Thomas (2006). JFLAP: Eine interaktive formelle Sprachen und ein Automatenpaket (1. Aufl.). Sudbury, MA: Jones und Bartlett. ISBN 978-0-7637-3834-1.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2. Aufl.). Boston Messe: Thomson -Kurs -Technologie. ISBN 978-0-534-95097-2.
• Holz, Derick (1987). Theorie der Berechnung (1. Aufl.). New York: Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.

Abstrakte Staatsmaschinen in der theoretischen Informatik

• Gurevich, Yuri (Juli 2000). "Sequentielle abstrakte Zustandsmaschinen erfassen sequentielle Algorithmen" (PDF). ACM -Transaktionen zur Rechenlogik. 1 (1): 77–111. Citeseerx 10.1.1.146.3017. doi:10.1145/343369.343384. S2CID 2031696.

Maschinelles Lernen mit Finite-State-Algorithmen

• Mitchell, Tom M. (1997). Maschinelles Lernen (1. Aufl.). New York: WCB/McGraw-Hill Corporation. ISBN 978-0-07-042807-2.

Hardware -Engineering: Zustandsminimierung und Synthese von sequentiellen Schaltungen

• Booth, Taylor L. (1967). Sequentielle Maschinen und Automatentheorie (1. Aufl.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Nummer 67-25924.
• Booth, Taylor L. (1971). Digitale Netzwerke und Computersysteme (1. Aufl.). New York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
• McCluskey, E. J. (1965). Einführung in die Theorie des Schaltens Schaltkreise (1. Aufl.). New York: McGraw-Hill Book Company, Inc. Library of Congress Card Catalog Nummer 65-17394.
• Hill, Fredrick J.; Peterson, Gerald R. (1965). Einführung in die Theorie des Schaltens Schaltkreise (1. Aufl.). New York: McGraw-Hill Book Company. Katalog Nummer 65-17394 der Library of Congress Card.

Finite Markov -Kettenprozesse

"Wir können an a denken Markov -Kette als ein Prozess, der sich nacheinander durch eine Reihe von Zuständen bewegt s₁, s₂,…, s_r. … Wenn es im Zustand ist s_i Es geht weiter zum nächsten Stopp zum Zustand s_j mit Wahrscheinlichkeit p_ij. Diese Wahrscheinlichkeiten können in Form einer Übergangsmatrix ausgestellt werden "(Kemeny (1959), S. 384)

Finite Markov-Kettenprozesse sind auch als bekannt als Subschüttungen endlicher Typ.

• Booth, Taylor L. (1967). Sequentielle Maschinen und Automatentheorie (1. Aufl.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Nummer 67-25924.
• Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite mathematische Strukturen (1. Aufl.). Englewood Cliffs, N.J.: Prentice-Hall, Inc. Library of Congress Card Catalog Nummer 59-12841. Kapitel 6 "Finite Markov -Ketten".

Externe Links

• Finite State Automata bei Curlie
• Modellierung eines einfachen KI -Verhaltens mit einer endlichen Zustandsmaschine Beispiel für die Nutzung in Videospielen
• Kostenloses Online-Wörterbuch des Computers Beschreibung von Finite-State-Maschinen
• NIST -Wörterbuch von Algorithmen und Datenstrukturen Beschreibung von Finite-State-Maschinen
• Ein kurzer Überblick über StatusmaschinentypenVergleich der theoretischen Aspekte von Maschinen Mealy, Moore, Harel und UML.