Eine Zustandsmaschine (FSM) oder Zustandsautomat (Mehrzahl-: Automaten), oder einfach eine Zustandmaschine, ist ein mathematisches Modell, das verwendet ist, um Computerprogramme und Digitallogikstromkreise zu entwerfen. Es wird als eine abstrakte Maschine konzipiert, die in einer einer begrenzten Zahl von Staaten sein kann. Die Maschine ist in nur einem Staat auf einmal; der Staat, in dem es zu jeder vorgegebenen Zeit ist, wird den aktuellen Staat genannt. Es kann sich von einem Staat bis einen anderen, wenn begonnen, durch ein Auslösen-Ereignis oder Bedingung ändern, das wird einen Übergang genannt. Ein besonderer FSM wird durch eine Liste der möglichen Übergang-Staaten von jedem aktuellen Staat und die Auslösen-Bedingung für jeden Übergang definiert.

Zustandsmaschinen können eine Vielzahl von Problemen modellieren, unter denen elektronische Designautomation, Nachrichtenprotokoll-Design, Syntaxanalyse und andere Technikanwendungen sind. In der Forschung der Biologie und künstlichen Intelligenz werden Zustandmaschinen oder Hierarchien von Zustandmaschinen manchmal verwendet, um neurologische Systeme zu beschreiben, und in der Linguistik können sie verwendet werden, um die Grammatiken von natürlichen Sprachen zu beschreiben.

Konzepte und Vokabular

Ein Staat beschreibt einen Verhaltensknoten des Systems, in dem er auf einen Abzug wartet, um einen Übergang durchzuführen. Normalerweise wird ein Staat eingeführt, wenn das System denselben Weg zu demselben Abzug nicht reagiert. Im Beispiel eines Autoradiosystems, wenn er (im Radiostaat) Radio hört, bedeutet der "folgende" Stimulus, zur folgenden Station zu gehen. Aber wenn das System im CD-Staat ist, bedeutet der "folgende" Stimulus, zur folgenden Spur zu gehen. Derselbe Stimulus löst verschiedene Handlungen abhängig vom aktuellen Staat aus. In einigen Zustandsmaschinendarstellungen ist es auch möglich, Handlungen zu einem Staat zu vereinigen:

• Zugang-Handlung: Der durchgeführt wird, wenn man in den Staat, eingeht
• Ausgangshandlung: Der durchgeführt wird, wenn man über den Staat herrscht.

Ein Übergang ist eine Reihe von durchzuführenden Handlungen, wenn eine Bedingung erfüllt wird, oder wenn ein Ereignis erhalten wird.

Darstellungen

Für eine Einführung, sieh Zustandsdiagramm.

Tisch des Staates/Ereignisses

Mehrere Zustandübergang-Tabellentypen werden verwendet. Die allgemeinste Darstellung wird unten gezeigt: die Kombination des aktuellen Staates (z.B. B) und Eingang (z.B. Y) zeigt den folgenden Staat (z.B. C). Die ganze Handlungsinformation wird im Tisch nicht direkt beschrieben und kann nur mit Kommentaren hinzugefügt werden. Eine FSM Definition einschließlich der vollen Handlungsinformation ist mögliche Verwenden-Zustandtabellen (sieh auch VFSM).

Maschinen des Staates UML

Die Vereinigte modellierende Sprache hat eine Notation, um Zustandmaschinen zu beschreiben. Maschinen des Staates UML überwinden die Beschränkungen von traditionellen Zustandsmaschinen, während sie ihre Hauptvorteile behalten. Maschinen des Staates UML führen die neuen Konzepte von hierarchisch verschachtelten Staaten und orthogonalen Gebieten ein, während sie den Begriff von Handlungen erweitern. Maschinen des Staates UML haben die Eigenschaften sowohl von Mehligen Maschinen als auch von Maschinen von Moore. Sie unterstützen Handlungen, die sowohl vom Staat des Systems als auch vom Auslösen-Ereignis, als in Mehligen Maschinen, sowie Zugang und Ausgangshandlungen abhängen, die mit Staaten aber nicht Übergängen, als in Maschinen von Moore vereinigt werden.

Maschinen des Staates SDL

Die Spezifizierungs- und Beschreibungssprache ist ein Standard von ITU, der Bildzeichen einschließt, um Handlungen im Übergang zu beschreiben:

• senden Sie ein Ereignis
• erhalten Sie ein Ereignis
• fangen Sie einen Zeitmesser an
• annullieren Sie einen Zeitmesser
• fangen Sie eine andere gleichzeitige Zustandmaschine an
• Entscheidung

SDL bettet grundlegende Datentypen genannt Abstrakte Datentypen, eine Handlungssprache und eine semantische Ausführung ein, um die Zustandsmaschine rechtskräftig zu machen.

Andere Zustandsdiagramme

Es gibt eine Vielzahl von Varianten, um einen FSM wie derjenige in der Abbildung 3 zu vertreten.

Gebrauch

Zusätzlich zu ihrem Gebrauch im Modellieren reaktiver Systeme hat hier präsentiert, Zustandsautomaten sind in vielen verschiedenen Gebieten, einschließlich Elektrotechnik, Linguistik, Informatik, Philosophie, Biologie, Mathematik und Logik bedeutend. Zustandsmaschinen sind eine Klasse von Automaten, die in der Automaten-Theorie und der Theorie der Berechnung studiert sind.

In der Informatik werden Zustandsmaschinen im Modellieren des Anwendungsverhaltens, Design der Hardware Digitalsysteme, Softwaretechnik, Bearbeiter, Netzprotokolle und die Studie der Berechnung und Sprachen weit verwendet.

Klassifikation

Es gibt zwei verschiedene Gruppen von Zustandmaschinen: Acceptors/Recognizers und Wandler.

Annehmer und recognizers

Annehmer und recognizers (auch Folge-Entdecker) erzeugen eine binäre Produktion, entweder ja sagend oder nicht zu antworten, ob der Eingang durch die Maschine akzeptiert wird oder nicht. Wie man sagt, akzeptieren alle Staaten des FSM entweder oder akzeptieren nicht. Wenn der ganze Eingang bearbeitet wird, wenn der aktuelle Staat ein akzeptierender Staat ist, wird der Eingang akzeptiert; sonst wird es zurückgewiesen. In der Regel ist der Eingang Symbole (Charaktere); Handlungen werden nicht verwendet. Das Beispiel in der Abbildung 4 zeigt eine Zustandsmaschine, die das "nette" Wort akzeptiert. In diesem FSM ist der einzige akzeptierende Staat Nummer 7.

Die Maschine kann auch als das Definieren einer Sprache beschrieben werden, die jedes Wort enthalten würde, das durch die Maschine, aber keinen der zurückgewiesenen akzeptiert ist; wir sagen dann, dass die Sprache durch die Maschine akzeptiert wird. Definitionsgemäß sind die durch FSMs akzeptierten Sprachen die regelmäßigen Sprachen — d. h. eine Sprache ist regelmäßig, wenn es einen FSM gibt, der es akzeptiert.

Fangen Sie Staat an

Der Anfang-Staat wird gewöhnlich gezogen mit einem Pfeil gezeigt, "darauf von irgendwelchem wo hinweisend" (Sipser (2006) p. 34).

Akzeptieren Sie (oder endgültig) Staaten

Akzeptieren Sie, dass Staaten (auch gekennzeichnet als das Annehmen oder die Endstaaten) diejenigen sind, an denen die Maschine berichtet, dass die Eingangsschnur, wie bearbeitet, bis jetzt, ein Mitglied der Sprache ist, die es akzeptiert. Es wird gewöhnlich durch einen doppelten Kreis vertreten.

Ein Beispiel eines akzeptierenden Staates erscheint im Diagramm nach rechts: Ein deterministischer begrenzter Automat (DFA), der entdeckt, ob die binäre Eingangsschnur eine gerade Zahl von 0's enthält.

S (der auch der Anfang-Staat ist) zeigt den Staat an, an dem eine gerade Zahl von 0's eingegeben worden ist. S ist deshalb ein akzeptierender Staat. Diese Maschine wird in einem akzeptieren Staat fertig sein, wenn die binäre Schnur eine gerade Zahl von 0's (einschließlich einer binärer Schnur enthält, die Nr. 0's enthält). Beispiele von durch diesen DFA akzeptierten Schnuren sind Epsilon (die leere Schnur), 1, 11, 11..., 00, 010, 1010, 10110, usw...

Wandler

Wandler erzeugen Produktion, die auf einem gegebenen Eingang und/oder einem Zustandverwenden Handlungen gestützt ist. Sie werden für Kontrollanwendungen und im Feld der linguistischen Datenverarbeitung verwendet. Hier sind zwei Typen bemerkenswert:

Maschine von Moore: Der FSM verwendet nur Zugang-Handlungen, d. h. Produktion hängt nur vom Staat ab. Der Vorteil des Modells von Moore ist eine Vereinfachung des Verhaltens. Denken Sie eine Aufzug-Tür. Die Zustandmaschine erkennt zwei Befehle an: "Command_open" und "command_close", die Zustandsänderungen auslösen. Die Zugang-Handlung (E:) in "Öffnenden" Zustandanfängen ein Motor, der die Tür, die Zugang-Handlung in Zustand"Schluss"-Anfängen ein Motor in der anderen Richtung öffnet, die die Tür schließt. Staaten "Geöffneter" und "Geschlossener" Halt der Motor, wenn völlig geöffnet oder geschlossen. Sie geben zur Außenwelt (z.B, zu anderen Zustandmaschinen) der Situation Zeichen: "Tür ist offene" oder "Tür wird geschlossen".

Mehlige Maschine: Der FSM verwendet nur Eingangshandlungen, d. h. Produktion hängt von Eingang und Staat ab. Der Gebrauch eines Mehligen FSM führt häufig zur Verminderung der Zahl von Staaten. Das Beispiel in der Abbildung 7 zeigt einem Mehligen FSM das Einführen desselben Verhaltens wie im Beispiel von Moore (das Verhalten hängt vom durchgeführten FSM Ausführungsmodell ab und, wird z.B, für virtuellen FSM, aber nicht für das Ereignis gesteuerter FSM arbeiten). Es gibt zwei Eingangshandlungen (ich:): "Fangen Sie Motor an, um die Tür zu schließen, wenn command_close ankommt" und "Motor in der anderen Richtung anfangen, um die Tür zu öffnen, wenn command_open ankommt". Die "Öffnung" und "Schluss"-Zwischenstaaten werden nicht gezeigt.

In der Praxis werden Mischmodelle häufig verwendet.

Mehr Details über die Unterschiede und den Gebrauch von Moore und Mehligen Modellen, einschließlich eines rechtskräftigen Beispiels, können im technischen Außenzeichen "Moore oder Mehliges Modell gefunden werden?"

Determinismus

Eine weitere Unterscheidung ist zwischen dem deterministischen (DFA) und nichtdeterministisch (NFA, GNFA) Automaten. In deterministischen Automaten hat jeder Staat genau einen Übergang für jeden möglichen Eingang. In nichtdeterministischen Automaten kann ein Eingang ein, mehr als ein oder kein Übergang für einen gegebenen Staat führen. Diese Unterscheidung ist in der Praxis, aber nicht in der Theorie wichtig, weil dort ein Algorithmus besteht (der powerset Aufbau), der jeden NFA in einen komplizierteren DFA mit der identischen Funktionalität umgestalten kann.

Der FSM mit nur einem Staat wird einen kombinatorischen FSM genannt und verwendet nur Eingangshandlungen. Dieses Konzept ist in Fällen nützlich, wo mehrere FSM erforderlich sind zusammenzuarbeiten, und wo es günstig ist, einen rein kombinatorischen Teil als eine Form von FSM zu betrachten, um den Designwerkzeugen anzupassen.

Alternative Semantik

Es gibt andere Sätze der Semantik, die verfügbar ist, um Zustandmaschinen zu vertreten. Zum Beispiel gibt es Werkzeuge, um Logik für eingebettete Kontrolleure zu modellieren und zu entwerfen. Sie verbinden hierarchische Zustandmaschinen, Fluss-Graphen und Wahrheitstabellen in eine Sprache, auf einen verschiedenen Formalismus und Satz der Semantik hinauslaufend. Abbildung 8 illustriert diese Mischung von Zustandmaschinen und Fluss-Graphen mit einer Reihe von Staaten, um den Staat einer Stoppuhr und eines Fluss-Graphen zu vertreten, um die Zecken der Bewachung zu kontrollieren. Diese Karten, wie die ursprünglichen Zustandmaschinen von Harel, unterstützen hierarchisch verschachtelte Staaten, orthogonale Gebiete, Zustandhandlungen und Übergang-Handlungen.

FSM Logik

Der folgende Staat und die Produktion eines FSM sind eine Funktion des Eingangs und vom aktuellen Staat. Die FSM Logik wird in der Abbildung 8 gezeigt.

Mathematisches Modell

In Übereinstimmung mit der allgemeinen Klassifikation werden die folgenden formellen Definitionen gefunden:

• Eine deterministische Zustandsmaschine oder Annehmer deterministische Zustandsmaschine sind ein fünffacher, wo:
• ist das Eingangsalphabet (ein begrenzter, nichtleerer Satz von Symbolen).
• ist ein begrenzter, nichtleerer Satz von Staaten.
• ist ein anfänglicher Staat, ein Element dessen.
• ist die Zustandübergang-Funktion: (In einem nichtdeterministischen begrenzten Automaten würde es sein, d. h., würde eine Reihe von Staaten zurückgeben).
• ist der Satz von Endstaaten, (vielleicht leer) Teilmenge dessen.

Sowohl für deterministischen als auch für nichtdeterministischen FSMs ist es herkömmlich, um zu erlauben, eine teilweise Funktion zu sein, d. h. muss für jede Kombination nicht definiert werden und. Wenn ein FSM in einem Staat ist, ist das folgende Symbol und wird nicht definiert, kann dann einen Fehler bekannt geben (d. h. den Eingang zurückweisen). Das ist in Definitionen von allgemeinen Zustandmaschinen nützlich, aber weniger nützlich, wenn es die Maschine umgestaltet. Einige Algorithmen in ihrer Verzug-Form können Gesamtfunktionen verlangen.

Eine Zustandsmaschine ist eine eingeschränkte Maschine von Turing, wo der Kopf nur "gelesene" Operationen durchführen kann, und sich immer vom linken bis Recht bewegt.

• Ein Zustandswandler ist ein sechsfacher, wo:

• ist das Eingangsalphabet (ein begrenzter nicht leerer Satz von Symbolen).

• ist das Produktionsalphabet (ein begrenzter, nichtleerer Satz von Symbolen).

• ist ein begrenzter, nichtleerer Satz von Staaten.

• ist der anfängliche Staat, ein Element dessen. In einem nichtdeterministischen begrenzten Automaten, ist eine Reihe anfänglicher Staaten.

• ist die Zustandübergang-Funktion:.

• ist die Produktionsfunktion.

Wenn die Produktionsfunktion eine Funktion eines staatlichen und Eingangsalphabetes ist , dass Definition dem Mehligen Modell entspricht, und als eine Mehlige Maschine modelliert werden kann. Wenn die Produktionsfunktion nur von einem Staat abhängt , dass Definition dem Modell von Moore entspricht, und als eine Maschine von Moore modelliert werden kann. Eine Zustandsmaschine ohne Produktionsfunktion ist überhaupt als ein Halbautomat oder Übergang-System bekannt.

Wenn wir das erste Produktionssymbol einer Maschine von Moore ignorieren, dann kann es zu einer mit der Produktion gleichwertigen Mehligen Maschine durch das Setzen der Produktionsfunktion jedes Mehligen Übergangs (d. h. das Beschriften jedes Randes) mit dem Produktionssymbol sogleich umgewandelt werden, das des Bestimmungsortes Staat von Moore gegeben ist. Die gegenteilige Transformation ist weniger aufrichtig, weil ein Mehliger Maschinenstaat verschiedene Produktionsetiketten auf seinen eingehenden Übergängen (Ränder) haben kann. Jeder solcher Staat muss in vielfachen Maschinenstaaten von Moore, ein für jedes Ereignis-Produktionssymbol gespalten werden.

Optimierung

Die Optimierung eines FSM bedeutet, die Maschine mit der minimalen Zahl von Staaten zu finden, die dieselbe Funktion durchführt. Der schnellste bekannte Algorithmus, der das tut, ist der Minimierungsalgorithmus von Hopcroft. Andere Techniken schließen das Verwenden einer Implikationstabelle oder des Verminderungsverfahrens von Moore ein. Zusätzlich acyclic kann FSAs in der geradlinigen Zeit Revuz (1992) minimiert werden.

Durchführung

Hardware-Anwendungen

In einem Digitalstromkreis kann ein FSM mit einem programmierbaren Logikgerät, einem programmierbaren Logikkontrolleur, Logiktoren und Flip-Misserfolgen oder Relais gebaut werden. Mehr spezifisch verlangt eine Hardware-Durchführung, dass ein Register Zustandsgrößen, einen Block der combinational Logik versorgt, die den Zustandübergang und einen zweiten Block der combinational Logik bestimmt, die die Produktion eines FSM bestimmt. Eine der klassischen Hardware-Durchführungen ist der Kontrolleur von Richards.

Mehlig und Maschinen von Moore erzeugen Logik mit der asynchronen Produktion, weil es eine Fortpflanzungsverzögerung zwischen der Zehensandale und Produktion gibt. Das verursacht langsamere Betriebsfrequenzen in FSM. Eine Mehlige Maschine oder Maschine von Moore können zu einem FSM konvertierbar sein, der Produktion direkt von einer Zehensandale ist, die den FSM geführt an höheren Frequenzen macht. Diese Art von FSM wird manchmal Medvedev FSM genannt. Ein Schalter ist die einfachste Form dieser Art von FSM.

Softwareanwendungen

Die folgenden Konzepte werden allgemein verwendet, um Softwareanwendungen mit Zustandsmaschinen zu bauen:

• Automaten-basierte Programmierung
• Ereignis gesteuerter FSM
• Virtueller FSM (VFSM)

Siehe auch

• Abstrakte Zustandmaschinen (ASM)
• Künstliche Intelligenz (AI)
• Abstrakte Staatsmaschinensprache (AsmL)
• Regelsystem
• Steuertabelle
• Entscheidungstische
• DEVS: Getrenntes Ereignis-Pflichtenheft
• Verlängerte Zustandsmaschine (EFSM)
• Zustandsmaschine mit datapath
• Verborgenes Modell von Markov
• Netz von Petri
• Automat von Pushdown
• Quant begrenzte Automaten (QFA)
• Erkennbare Sprache
• Folgende Logik
• Spezifizierung und Beschreibungssprache
• Zustandsdiagramm
• Übergang-System
• Baumautomat
• Maschine von Turing
• Maschine des Staates UML
• SCXML

Weiterführende Literatur

Allgemein

• Wagner, F., "Software mit Zustandsmaschinen modellierend: Eine Praktische Annäherung", Veröffentlichungen von Auerbach, 2006, internationale Standardbuchnummer 0-8493-8086-3.
• ITU-T, Spezifizierung der Empfehlung Z.100 und Beschreibungssprache (SDL)
• Samek, M., Praktischer Statecharts in C/C ++, CMP Bücher, 2002, internationale Standardbuchnummer 1-57820-110-1.
• Samek, M., Praktischer UML Statecharts in C/C ++, 2. Ausgabe, Newnes, 2008, internationale Standardbuchnummer 0-7506-8706-1.
• Gardner, T., Fortgeschrittenes Staatsmanagement, 2007
• Kassandra, C., Lafortune, S., "Einführung in Getrennte Ereignis-Systeme". Kluwer, 1999, internationale Standardbuchnummer 0-7923-8609-4.
• Timothy Kam, Synthese von Zustandsmaschinen: Funktionelle Optimierung. Kluwer Akademische Herausgeber, Boston 1997, internationale Standardbuchnummer 0-7923-9842-4
• Die Villa Tiziano, Synthese von Zustandsmaschinen: Logikoptimierung. Kluwer Akademische Herausgeber, Boston 1997, internationale Standardbuchnummer 0-7923-9892-0
• Carroll, J., Lange, D., Theorie von Begrenzten Automaten mit einer Einführung in Formelle Sprachen. Prentice Hall, Englewood Klippen, 1989.
• Kohavi, Z., Umschaltend und Begrenzte Automaten-Theorie. McGraw-Hügel, 1978.
• Kieme, A., Einführung in die Theorie von Zustandsmaschinen. McGraw-Hügel, 1962.
• Ginsburg, S., Eine Einführung in die Mathematische Maschinentheorie. Addison-Wesley, 1962.

Zustandsmaschinen (Automaten-Theorie) in der theoretischen Informatik

• Umfassendes, weiträumiges Buch, das für Fachmänner beabsichtigt ist, die für beide theoretischen Computerwissenschaftler sowie Elektroingenieure geschrieben sind. Mit ausführlichen Erklärungen von Zustandminimierungstechniken, FSMs, Maschinen von Turing, Prozessen von Markov und Unentscheidbarkeit. Ausgezeichnete Behandlung von Prozessen von Markov.
• Ausgezeichnet. Ist im Druck in verschiedenen Ausgaben und Nachdrücken seit 1974 (1974, 1980, 1989, 1999) gewesen.
• Annäherungskirch-Turing-These von drei Winkeln: Niveaus von begrenzten Automaten als Annehmer von formellen Sprachen, primitiver und teilweiser rekursiver Theorie und Macht von Programmiersprachen der bloßen Knochen, Algorithmen, alle in einem schlankem Volumen durchzuführen.
• Ein ausgezeichnetes Buch hat um die Probleme der Maschineninterpretation von "Sprachen", NP-Vollständigkeit usw. im Mittelpunkt gestanden.
• Ausgesprochen verschieden und weniger Einschüchtern-als die Erstausgabe.
• Minsky gibt das Definieren der Seiten 11-20 aus, was ein "Staat" im Zusammenhang von FSMs ist. Seine Zustandsdiagramm-Tagung ist unkonventionell. Ausgezeichnet, d. h., relativ lesbar, manchmal komisch.
• Abstrakte Algebra ist am Kern des Buches, das Machen davon ist vorwärts gegangen und weniger zugänglich als andere Texte.
• vgl Zustandsmaschinen (begrenzte Automaten) im Kapitel 29.

Abstrakte Zustandmaschinen in der theoretischen Informatik

• Yuri Gurevich (2000), Folgende Abstrakte Staatsmaschinenfestnahme Folgende Algorithmen, ACM Transaktionen auf der Rechenbetonten Logik, vl. 1, Nr. 1 (Juli 2000), Seiten 77-111.

http://research.microsoft.com/~gurevich/Opera/141.pdf

Maschine, die erfährt, Zustandsalgorithmen verwendend

• Eine breite Bürste, aber ziemlich gründlich und manchmal schwierig, beabsichtigt für Computerwissenschaftler und Ingenieure. Verstärkung des Kapitels 13, die Geschäfte mit dem Roboter erfahrenden Beteiligen von Algorithmen Erfährt, "setzt Maschine wie fest".

Hardware-Technik: Zustandminimierung und Synthese von folgenden Stromkreisen

Umfassendes, weiträumiges Buch, das für Fachmänner beabsichtigt ist, die für beide theoretischen Computerwissenschaftler sowie Elektroingenieure geschrieben sind. Mit ausführlichen Erklärungen von Zustandminimierungstechniken, FSMs, Maschinen von Turing, Prozessen von Markov und Unentscheidbarkeit. Ausgezeichnete Behandlung von Prozessen von Markov.

• Beabsichtigt für Elektroingenieure. Mehr eingestellt, weniger anspruchsvoll als sein früheres Buch. Seine Behandlung von Computern ist überholt. Interessant nehmen auf der Definition "des Algorithmus".
• Beabsichtigt für Hardware-Elektroingenieure. Mit ausführlichen Erklärungen von Zustandminimierungstechniken und Synthese-Techniken für das Design von combinatory Logikstromkreisen.
• Beabsichtigt für Hardware-Elektroingenieure. Ausgezeichnete Erklärungen von Zustandminimierungstechniken und Synthese-Techniken für das Design von combinatory und folgenden Logikstromkreisen.

Begrenzte Kettenprozesse von Markov

:: "Wir können an eine Kette von Markov als ein Prozess denken, der sich nacheinander durch eine Reihe von Staaten s, s..., s bewegt...., wenn es im Staat s ist, geht es zum folgenden Halt weiter, um s mit der Wahrscheinlichkeit p festzusetzen. Diese Wahrscheinlichkeiten können in der Form einer Übergang-Matrix ausgestellt werden" (Kemeny (1959), p. 384)

Begrenzte Markov-Kettenprozesse sind auch bekannt als Subverschiebungen des begrenzten Typs.

Umfassendes, weiträumiges Buch, das für Fachmänner beabsichtigt ist, die für beide theoretischen Computerwissenschaftler sowie Elektroingenieure geschrieben sind. Mit ausführlichen Erklärungen von Zustandminimierungstechniken, FSMs, Maschinen von Turing, Prozessen von Markov und Unentscheidbarkeit. Ausgezeichnete Behandlung von Prozessen von Markov.

• Klassischer Text. vgl Kapitel 6 "Begrenzte Ketten von Markov".

Links

• Freies Online-Wörterbuch der Rechenbeschreibung von Zustandsmaschinen
• NIST Wörterbuch der Algorithmus- und Datenstruktur-Beschreibung von Zustandsmaschinen