Endlicher Automat - Finite-state machine

Combinational logic Finite-state machine Pushdown automaton Turing machine Automata theoryAutomatentheorie.svg
Über dieses Bild
Klassen von Automaten
(Wenn Sie auf jede Ebene klicken, erhalten Sie einen Artikel zu diesem Thema)

Ein endlicher Automat ( FSM ) oder ein endlicher Automat ( FSA , Plural: Automaten ), ein endlicher Automat oder einfach ein Zustandsautomat ist ein mathematisches Berechnungsmodell . Es ist eine abstrakte Maschine , die sich zu jeder Zeit in genau einem von endlich vielen Zuständen befinden kann. Der FSM kann als Reaktion auf einige Eingaben von einem Zustand in einen anderen wechseln ; der Wechsel von einem Zustand in einen anderen wird als Übergang bezeichnet . Ein FSM wird durch eine Liste seiner Zustände, seines Anfangszustands und der Eingänge definiert, die jeden Übergang auslösen. Es gibt zwei Arten von endlichen Automaten – deterministische endliche Automaten und nicht-deterministische endliche Automaten . Ein deterministischer endlicher Automat kann äquivalent zu jedem nicht-deterministischen konstruiert werden.

Das Verhalten von Zustandsautomaten lässt sich in vielen Geräten der modernen Gesellschaft beobachten, die in Abhängigkeit von einer ihnen präsentierten Ereignisfolge eine vorgegebene Abfolge von Aktionen ausführen. Einfache Beispiele sind Verkaufsautomaten , die Produkte ausgeben, wenn die richtige Kombination von Münzen eingeworfen wird, Aufzüge , deren Haltestellenfolge durch die von den Fahrgästen angeforderten Stockwerke bestimmt wird, Ampeln , die die Reihenfolge ändern, wenn Autos warten, und Kombinationsschlösser , die die Eingabe einer Zahlenfolge in der richtigen Reihenfolge.

Der endliche Automat hat weniger Rechenleistung als einige andere Rechenmodelle wie die Turing-Maschine . Die Rechenleistungsunterscheidung bedeutet, dass es Rechenaufgaben gibt, die eine Turing-Maschine ausführen kann, eine FSM jedoch nicht. Dies liegt daran, dass der Speicher eines FSM durch die Anzahl seiner Zustände begrenzt ist. Eine endliche Maschine hat die gleiche Rechenleistung wie eine Turing-Maschine , die so eingeschränkt ist, dass ihr Kopf nur "Lese"-Operationen ausführen darf und sich immer von links nach rechts bewegen muss. FSMs werden im allgemeineren Bereich der Automatentheorie studiert .

Beispiel: Münzdrehkreuz

Zustandsdiagramm für ein Drehkreuz
Ein Drehkreuz

Ein Beispiel für einen einfachen Mechanismus, der von einer Zustandsmaschine modelliert werden kann, ist ein Drehkreuz . Ein Drehkreuz, das verwendet wird, um den Zugang zu U-Bahnen und Fahrgeschäften zu kontrollieren, ist ein Tor mit drei rotierenden Armen in Hüfthöhe, einer über dem Eingang. Anfänglich sind die Arme verriegelt, wodurch der Eingang blockiert wird und die Gäste daran gehindert werden, durchzukommen. Das Einwerfen einer Münze oder eines Tokens in einen Schlitz am Drehkreuz entriegelt die Arme, sodass ein einzelner Kunde hindurchstoßen kann. Nach dem Passieren des Kunden werden die Arme wieder verriegelt, bis eine weitere Münze eingeworfen wird.

Als Zustandsmaschine betrachtet, hat das Drehkreuz zwei mögliche Zustände: Gesperrt und Entsperrt . Es gibt zwei mögliche Eingaben, die seinen Zustand beeinflussen: eine Münze in den Schlitz stecken ( coin ) und den Arm drücken ( push ). Im verriegelten Zustand hat das Drücken auf den Arm keine Wirkung; Ganz gleich , wie oft der Eingang Push gegeben ist, es bleibt im verriegelten Zustand. Setzen Sie eine Münze in - das heißt, eine Maschine zu geben Münze Eingang - verschiebt den Zustand von Locked zu entriegelte . Im entsperrten Zustand hat das Einwerfen zusätzlicher Münzen keine Wirkung; das heißt, zusätzlich zu geben coin Eingänge nicht den Zustand ändern. Wenn ein Kunde jedoch durch die Arme drückt und eine Push- Eingabe gibt, verschiebt sich der Zustand zurück auf Gesperrt .

Die Drehkreuz-Zustandsmaschine kann durch eine Zustandsübergangstabelle dargestellt werden , die für jeden möglichen Zustand die Übergänge zwischen ihnen (basierend auf den an die Maschine gegebenen Eingaben) und die aus jeder Eingabe resultierenden Ausgaben anzeigt:

Aktuellen Zustand Eingang Nächster Staat Ausgabe
Gesperrt Münze Entsperrt Entriegelt das Drehkreuz, damit der Kunde sich durchsetzen kann.
drücken Gesperrt Keiner
Entsperrt Münze Entsperrt Keiner
drücken Gesperrt Wenn der Kunde durchgedrückt hat, verriegelt das Drehkreuz.

Die Drehkreuz-Zustandsmaschine kann auch durch einen gerichteten Graphen dargestellt werden, der als Zustandsdiagramm (oben) bezeichnet wird . Jeder Zustand wird durch einen Knoten ( Kreis ) repräsentiert . Kanten ( Pfeile ) zeigen die Übergänge von einem Zustand in einen anderen. Jeder Pfeil ist mit der Eingabe beschriftet, die diesen Übergang auslöst. Ein Eingang, der nicht eine Zustandsänderung (beispielsweise eine Ursache coin Eingabe in der entriegelte in dem ursprünglichen Zustand state) zurückkehrt , durch einen kreisförmigen Pfeil dargestellt. Der Pfeil in den Locked- Knoten vom schwarzen Punkt zeigt an, dass es sich um den Anfangszustand handelt.

Konzepte und Terminologie

Ein Zustand ist eine Beschreibung des Zustands eines Systems, das darauf wartet, einen Übergang auszuführen . Eine Transition ist eine Reihe von Aktionen, die ausgeführt werden sollen, wenn eine Bedingung erfüllt oder ein Ereignis empfangen wird. Wenn beispielsweise ein Audiosystem zum Radiohören verwendet wird (das System befindet sich im "Radio"-Zustand), führt der Empfang eines "nächsten" Stimulus zum Wechsel zum nächsten Sender. Wenn sich das System im "CD"-Zustand befindet, führt der "nächste" Stimulus zum Übergang zum nächsten Track. Identische Reize lösen je nach aktuellem Zustand unterschiedliche Aktionen aus.

In einigen endlichen Automatendarstellungen ist es auch möglich, Aktionen einem Zustand zuzuordnen:

  • eine Eintrittsaktion: wird beim Eintritt in den Zustand ausgeführt, und
  • eine Exit-Aktion: Wird beim Verlassen des Zustands ausgeführt.

Vertretungen

Abb. 1 Beispiel für ein UML-Zustandsdiagramm (ein Toaster)
Abb. 2 Beispiel einer SDL-Zustandsmaschine
Abb. 3 Beispiel eines einfachen endlichen Automaten

Status-/Ereignistabelle

Es werden mehrere Zustandsübergangstabellentypen verwendet. Nachfolgend die gängigste Darstellung: Die Kombination aus aktuellem Zustand (zB B) und Eingang (zB Y) zeigt den nächsten Zustand (zB C). Die Informationen der kompletten Aktion sind in der Tabelle nicht direkt beschrieben und können nur über Fußnoten ergänzt werden. Eine FSM-Definition einschließlich der vollständigen Aktionsinformationen ist über Zustandstabellen möglich (siehe auch virtuelle endliche Automaten ).

Zustandsübergangstabelle
  Aktueller
Status
Eingang
Zustand A Zustand B Zustand C
Eingabe X ... ... ...
Eingabe Y ... Zustand C ...
Eingabe Z ... ... ...

UML-Zustandsautomaten

Die Unified Modeling Language hat eine Notation zur Beschreibung von Zustandsautomaten. UML-Zustandsautomaten überwinden die Einschränkungen traditioneller endlicher Automaten und behalten gleichzeitig ihre Hauptvorteile bei. UML-Zustandsautomaten führen die neuen Konzepte von hierarchisch verschachtelten Zuständen und orthogonalen Regionen ein und erweitern gleichzeitig den Begriff der Aktionen . UML-Zustandsautomaten haben die Eigenschaften sowohl von Mealy-Maschinen als auch von Moore-Maschinen . Sie unterstützen Aktionen , die sowohl vom Zustand des Systems als auch vom auslösenden Ereignis abhängen , wie in Mealy-Maschinen, sowie Ein- und Austrittsaktionen , die wie in Moore-Maschinen mit Zuständen und nicht mit Übergängen verbunden sind.

SDL-Zustandsautomaten

Die Spezifikations- und Beschreibungssprache ist ein Standard von ITU , der grafische Symbole enthält, um Aktionen beim Übergang zu beschreiben:

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

SDL bettet grundlegende Datentypen namens "Abstrakte Datentypen", eine Aktionssprache und eine Ausführungssemantik ein, um die endliche Zustandsmaschine ausführbar zu machen.

Andere Zustandsdiagramme

Es gibt eine Vielzahl von Varianten, um eine FSM wie die in Abbildung 3 darzustellen.

Verwendungszweck

Neben ihrer Verwendung bei der hier vorgestellten Modellierung reaktiver Systeme sind endliche Automaten in vielen verschiedenen Bereichen von Bedeutung, darunter Elektrotechnik , Linguistik , Informatik , Philosophie , Biologie , Mathematik , Videospielprogrammierung und Logik . Endliche Automaten sind eine Klasse von Automaten, die in der Automatentheorie und der Rechentheorie untersucht werden . In der Informatik werden endliche Automaten häufig bei der Modellierung des Anwendungsverhaltens, dem Design digitaler Hardwaresysteme , der Softwareentwicklung , Compilern , Netzwerkprotokollen und dem Studium von Berechnungen und Sprachen verwendet.

Einstufung

Endliche Automaten können in Akzeptoren, Klassifikatoren, Transducer und Sequencer unterteilt werden.

Akzeptoren

Abb. 4: Acceptor FSM: Parsen des Strings "nice".
Abb. 5: Darstellung eines Akzeptors; Dieses Beispiel zeigt eines, das bestimmt, ob eine Binärzahl eine gerade Zahl von Nullen hat, wobei S 1 ein akzeptierender Zustand und S 2 ein nicht akzeptierender Zustand ist .

Akzeptoren (auch als Detektoren oder Erkenner ) erzeugen Binärausgang, der angibt , ob oder nicht die empfangene Eingabe akzeptiert wird. Jeder Zustand eines Akzeptors ist entweder akzeptierend oder nicht akzeptierend . Nachdem alle Eingaben empfangen wurden, wird die Eingabe akzeptiert, wenn der aktuelle Zustand ein akzeptierender Zustand ist; andernfalls wird es abgelehnt. Die Eingabe ist in der Regel eine Folge von Symbolen (Zeichen); 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 den String "nice" akzeptiert. In diesem Akzeptor ist der einzige akzeptierende Zustand Zustand 7.

Eine (möglicherweise unendliche) Menge von Symbolfolgen, die als formale Sprache bezeichnet wird , ist eine reguläre Sprache, wenn es einen Akzeptor gibt, der genau diese Menge akzeptiert . Zum Beispiel ist die Menge der Binärstrings mit einer geraden Anzahl von Nullen eine reguläre Sprache (vgl. Abb. 5), während die Menge aller Strings, deren Länge eine Primzahl ist, nicht ist.

Ein Akzeptor könnte auch so beschrieben werden, dass er eine Sprache definiert, die jede vom Akzeptor akzeptierte Zeichenfolge enthält, aber keine der zurückgewiesenen; diese Sprache wird vom Akzeptierenden akzeptiert . Per Definition sind die von Akzeptoren akzeptierten Sprachen die regulären Sprachen .

Das Problem der Bestimmung der von einem gegebenen Akzeptor akzeptierten Sprache ist eine Instanz des algebraischen Pfadproblems – selbst eine Verallgemeinerung des kürzesten Pfadproblems auf Graphen mit Kanten, die durch die Elemente eines (beliebigen) Semirings gewichtet werden .

Ein Beispiel für einen akzeptierenden Zustand zeigt Abb. 5: Ein deterministischer endlicher Automat (DFA), der erkennt, ob der binäre Eingabestring eine gerade Anzahl von Nullen enthält.

S 1 (was auch der Startzustand ist) zeigt den Zustand an, bei dem eine gerade Anzahl von Nullen eingegeben wurde. S 1 ist daher ein akzeptierender Zustand. Dieser Akzeptor endet in einem akzeptieren Zustand, wenn die Binärzeichenfolge eine gerade Anzahl von Nullen enthält (einschließlich aller Binärzeichenfolgen, die keine Nullen enthalten). Beispiele für Zeichenfolgen, die von diesem Akzeptor akzeptiert werden, sind ε (die leere Zeichenfolge ), 1, 11, 11..., 00, 010, 1010, 10110 usw.

Klassifikatoren

Klassifikatoren sind eine Verallgemeinerung von Akzeptoren, die eine n- äre Ausgabe erzeugen, wobei n strikt größer als zwei ist.

Wandler

Abb. 6 Wandler FSM: Moore-Modellbeispiel
Abb. 7 Transducer FSM: Beispiel eines Mealy-Modells

Wandler erzeugen eine Ausgabe basierend auf einer gegebenen Eingabe und/oder einem Zustand unter Verwendung von Aktionen. Sie werden für Steuerungsanwendungen und im Bereich der Computerlinguistik verwendet .

Bei Steuerungsanwendungen werden zwei Typen unterschieden:

Moore-Maschine
Die FSM verwendet nur Eingabeaktionen, dh die Ausgabe hängt nur vom Zustand ab. Der Vorteil des Moore-Modells ist eine Vereinfachung des Verhaltens. Betrachten Sie eine Aufzugstür. Die Zustandsmaschine kennt zwei Befehle: "command_open" und "command_close", die Zustandsänderungen auslösen. Die Eintrittsaktion (E:) im Zustand „Öffnen“ startet einen Motor zum Öffnen der Tür, die Eintrittsaktion im Zustand „Schließen“ startet einen Motor in die andere Richtung zum Schließen der Tür. Die Zustände "Geöffnet" und "Geschlossen" stoppen den Motor, wenn er vollständig geöffnet oder geschlossen ist. Sie signalisieren der Außenwelt (zB anderen Zustandsautomaten) die Situation: „Tür ist offen“ oder „Tür ist geschlossen“.
Mehlige Maschine
Der FSM verwendet auch Eingabeaktionen, dh die Ausgabe hängt von Eingabe und Zustand ab. Die Verwendung eines Mealy FSM führt oft zu einer Reduzierung der Anzahl der Zustände. Das Beispiel in Abbildung 7 zeigt einen Mealy FSM, der das gleiche Verhalten wie im Moore-Beispiel implementiert (das Verhalten hängt vom implementierten FSM-Ausführungsmodell ab und funktioniert zB für virtuelles FSM, aber nicht für ereignisgesteuertes FSM ). Es gibt zwei Eingabeaktionen (I:): "Motor starten, um die Tür zu schließen, wenn command_close ankommt" und "Motor in die andere Richtung starten, um die Tür zu öffnen, wenn command_open ankommt". Die Zwischenzustände "Öffnen" und "Schließen" sind nicht dargestellt.

Sequenzer

Sequenzer (auch Generatoren genannt ) sind eine Unterklasse von Akzeptoren und Wandlern, die ein aus einem Buchstaben bestehendes Eingabealphabet haben. Sie erzeugen nur eine Sequenz, die als Ausgabesequenz von Akzeptor- oder Transducer-Ausgaben angesehen werden kann.

Determinismus

Eine weitere Unterscheidung ist zwischen deterministischen ( DFA ) und nicht-deterministischen ( NFA , GNFA ) Automaten. In einem deterministischen Automaten hat jeder Zustand für jede mögliche Eingabe genau einen Übergang. In einem nicht-deterministischen Automaten kann eine Eingabe zu einem, mehreren oder keinem Übergang für einen gegebenen Zustand führen. Der Powerset-Konstruktionsalgorithmus kann jeden nichtdeterministischen Automaten in einen (normalerweise komplexeren) deterministischen Automaten mit identischer Funktionalität umwandeln.

Ein endlicher Automat mit nur einem Zustand wird als "kombinatorischer FSM" bezeichnet. Es erlaubt nur Aktionen beim Übergang in einen Zustand. Dieses Konzept ist in Fällen nützlich, in denen mehrere endliche Automaten zusammenarbeiten müssen und wenn es zweckmäßig ist, einen rein kombinatorischen Teil als eine Form von FSM zu betrachten, die den Entwurfswerkzeugen entspricht.

Alternative Semantik

Es gibt andere Sätze von Semantiken, die zur Darstellung von Zustandsautomaten verfügbar sind. So gibt es beispielsweise Tools zum Modellieren und Entwerfen von Logik für eingebettete Controller. Sie kombinieren hierarchische Zustandsautomaten (die normalerweise mehr als einen aktuellen Zustand haben), Flussgraphen und Wahrheitstabellen in einer Sprache, was zu einem anderen Formalismus und einer anderen Semantik führt. Diese Diagramme unterstützen wie die ursprünglichen Zustandsmaschinen von Harel hierarchisch verschachtelte Zustände, orthogonale Regionen , Zustandsaktionen und Übergangsaktionen.

Mathematisches Modell

Entsprechend der allgemeinen Klassifikation finden sich folgende formale Definitionen.

Ein deterministischer endlicher Automat oder ein deterministischer endlicher Akzeptor ist ein Fünftel , wobei:

  • ist das Eingangsalphabet (a finite nicht leere Menge von Symbolen);
  • ist eine endliche nichtleere Menge von Zuständen;
  • ist ein Anfangszustand, ein Element von ;
  • ist die Zustandsübergangsfunktion: (in einem nichtdeterministischen endlichen Automaten wäre sie , dh würde eine Menge von Zuständen zurückgeben);
  • ist die Menge der Endzustände, eine (möglicherweise leere) Teilmenge von .

Sowohl für deterministische als auch für nicht-deterministische FSMs ist es üblich, eine partielle Funktion zuzulassen , dh muss nicht für jede Kombination von und definiert werden . Befindet sich eine FSM in einem Zustand , ist das nächste Symbol definiert und nicht definiert, kann dann einen Fehler melden (dh die Eingabe verwerfen). Dies ist nützlich bei Definitionen von allgemeinen Zustandsautomaten, aber weniger nützlich bei der Transformation des Automaten. Einige Algorithmen in ihrer Standardform können Gesamtfunktionen erfordern.

Eine endliche Maschine hat die gleiche Rechenleistung wie eine Turing-Maschine , die so eingeschränkt ist, dass ihr Kopf nur "Lese"-Operationen ausführen darf und sich immer von links nach rechts bewegen muss. Das heißt, jede formale Sprache, die von einem endlichen Automaten akzeptiert wird, wird von einer solchen eingeschränkten Turing-Maschine akzeptiert und umgekehrt.

Ein endlicher Wandler ist ein Sechsfach , wobei:

  • ist das Eingangsalphabet (a finite nicht leere Menge von Symbolen);
  • ist das Ausgabealphabet (eine endliche nichtleere Menge von Symbolen);
  • ist eine endliche nichtleere Menge von Zuständen;
  • ist der Anfangszustand, ein Element von ;
  • ist die Zustandsübergangsfunktion: ;
  • ist die Ausgabefunktion.

Wenn die Ausgabefunktion vom Zustand und Eingabesymbol ( ) abhängt , entspricht diese Definition dem Mealy-Modell und kann als Mealy-Maschine modelliert werden . Wenn die Ausgabefunktion nur von state ( ) abhängt , entspricht diese Definition dem Moore-Modell und kann als Moore-Maschine modelliert werden . Ein endlicher Automat ohne Ausgabefunktion wird als Halbautomat oder Übergangssystem bezeichnet .

Wenn wir das erste Ausgabesymbol einer Moore-Maschine außer Acht lassen , dann kann sie leicht in eine ausgabeäquivalente Mealy-Maschine umgewandelt werden, indem die Ausgabefunktion jedes Mealy-Übergangs (dh jede Kante beschriftet) mit dem Ausgabesymbol des Ziels Moore Zustand. Die umgekehrte Transformation ist weniger einfach, da ein Mealy-Maschinenzustand unterschiedliche Ausgabelabels an seinen eingehenden Übergängen (Kanten) haben kann. Jeder dieser Zustände muss in mehrere Moore-Maschinenzustände aufgeteilt werden, einen für jedes auftretende Ausgabesymbol.

Optimierung

Eine FSM zu optimieren bedeutet, eine Maschine mit der minimalen Anzahl von Zuständen zu finden, die dieselbe Funktion ausführt. Der schnellste bekannte Algorithmus dafür ist der Hopcroft-Minimierungsalgorithmus . Andere Techniken umfassen die Verwendung einer Implikationstabelle oder das Moore-Reduktionsverfahren. Darüber hinaus können azyklische FSAs in linearer Zeit minimiert werden.

Implementierung

Hardwareanwendungen

Abb. 9 Das Schaltbild für einen 4-Bit- TTL- Zähler, eine Art Zustandsmaschine

In einer digitalen Schaltung kann ein FSM unter Verwendung einer programmierbaren Logikvorrichtung , einer programmierbaren Logiksteuerung , Logikgatter und Flip-Flops oder Relais aufgebaut werden . Genauer gesagt erfordert eine Hardwareimplementierung ein Register zum Speichern von Zustandsvariablen, einen Block kombinatorischer Logik , der den Zustandsübergang bestimmt, und einen zweiten Block kombinatorischer Logik, der die Ausgabe eines FSM bestimmt. Eine der klassischen Hardware-Implementierungen ist der Richards-Controller .

In einer Medvedev-Maschine ist der Ausgang direkt mit den Zustands-Flip-Flops verbunden, wodurch die Zeitverzögerung zwischen den Flip-Flops und dem Ausgang minimiert wird.

Die Durchzustandscodierung für Zustandsmaschinen mit niedrigem Stromverbrauch kann optimiert werden, um den Stromverbrauch zu minimieren.

Softwareanwendungen

Die folgenden Konzepte werden häufig verwendet, um Softwareanwendungen mit endlichen Automaten zu erstellen:

Endliche Automaten und Compiler

Finite Automaten werden häufig im Frontend von Programmiersprachen-Compilern verwendet. Ein solches Frontend kann mehrere endliche Automaten umfassen, die einen lexikalischen Analysator und einen Parser implementieren . Ausgehend von einer Zeichenfolge erstellt der lexikalische Analysator eine Folge von Sprachtoken (wie reservierte Wörter, Literale und Bezeichner), aus denen der Parser einen Syntaxbaum erstellt. Der lexikalische Analysator und der Parser behandeln die regulären und kontextfreien Teile der Grammatik der Programmiersprache.

Siehe auch

Verweise

Weiterlesen

Allgemein

Endliche Automaten (Automatentheorie) in der theoretischen Informatik

Abstrakte Zustandsautomaten in der theoretischen Informatik

Maschinelles Lernen mit endlichen 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. Kartenkatalognummer 67-25924 der Library of Congress.
  • Booth, Taylor L. (1971). Digitale Netzwerke und Computersysteme (1. Aufl.). New York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
  • McCluskey, EJ (1965). Einführung in die Theorie der Schaltkreise (1. Aufl.). New York: McGraw-Hill Book Company, Inc. Bibliothek des Kongresses Kartenkatalognummer 65-17394.
  • Hill, Fredrick J.; Peterson, Gerald R. (1965). Einführung in die Theorie der Schaltkreise (1. Aufl.). New York: McGraw-Hill-Buchgesellschaft. Katalognummer 65-17394 der Kongressbibliothek.

Finite Markov-Kettenprozesse

„Wir denken , kann aus einer Markow - Kette als ein Prozess, der sich bewegt nacheinander durch eine Reihe von Zuständen s 1 , s 2 , ..., s r ... . Wenn im Zustand s i geht es weiter zu der nächsten Station in den Zustand s j mit Wahrscheinlichkeit p ij . Diese Wahrscheinlichkeiten können in Form einer Übergangsmatrix dargestellt werden" (Kemeny (1959), S. 384)

Finite Markov-Ketten-Prozesse werden auch als Subshifts vom endlichen Typ bezeichnet .

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

Externe Links