Ich suche nach guten Beispielen für endliche Zustandsmaschinen; Sprache ist nicht besonders wichtig, nur gute Beispiele.

Code-Implementierungen sind nützlich (verallgemeinerter Pseudo-Code), aber es ist auch sehr nützlich, die verschiedenen Verwendungen von FSMs zu erfassen.

Beispiele müssen nicht unbedingt computerbasiert sein, zum Beispiel ist das Beispiel von Mike Dunlavey's Railroad Networks sehr nützlich.

A Safe (Ereignis ausgelöst)

• Staaten : Mehrere „gesperrt“ Staaten, ein „entriegelt“ Zustand
• Übergänge : Durch korrekte Kombinationen / Tasten gelangen Sie von den anfänglichen gesperrten Zuständen zu den gesperrten Zuständen, die näher an den entsperrten Zuständen liegen, bis Sie schließlich zum entsperrten Zustand gelangen. Falsche Kombinationen / Tasten versetzen Sie wieder in den ursprünglichen gesperrten Zustand (manchmal als Leerlauf bezeichnet) .

Ampel (Zeit ausgelöst | Sensor [Ereignis] ausgelöst)

• Zustände : ROT, GELB, GRÜN (einfachstes Beispiel)
• Übergänge : Wechseln Sie nach einem Timer von ROT zu GRÜN, von GRÜN zu GELB und von GELB zu ROT. Kann auch ausgelöst werden, wenn Autos in verschiedenen (komplizierteren) Zuständen erfasst werden.

Automaten (Ereignis ausgelöst, eine Variation des Safes )

• Staaten : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS, etc, VEND, CHANGE
• Übergänge : Statusänderungen beim Einwerfen von Münzen, Banknoten, Übergang zu VEND bei korrektem Kaufbetrag (oder mehr) und Übergang zu CHANGE oder IDLE (je nachdem, wie ethisch Ihr Verkaufsautomat ist)

Beispiel für das Border Gateway-Protokoll

BGP ist ein Protokoll, das die wichtigsten Routing-Entscheidungen im Internet unterstützt. Es verwaltet eine Tabelle, um die Erreichbarkeit von Hosts von einem bestimmten Knoten aus zu bestimmen, und macht das Internet wirklich dezentral.

Im Netzwerk ist jeder BGP- Knoten ein Peer und verwendet eine Finite-State-Maschine mit einem der sechs Zustände Idle , Connect , Active , OpenSent , OpenConfirm und Established . Jede Peer-Verbindung im Netzwerk behält einen dieser Zustände bei.

Das BGP-Protokoll bestimmt die Nachrichten, die an Peers gesendet werden, um ihren Status zu ändern.

BPG-Zustandsdiagramm.

Leerlauf

Der erste Zustand Leerlauf . In diesem Zustand initialisiert BGP Ressourcen, lehnt eingehende Verbindungsversuche ab und initiiert eine Verbindung zum Peer.

Verbinden

Der zweite Status Verbinden . In diesem Status wartet der Router, bis die Verbindung hergestellt wurde, und wechselt bei Erfolg in den OpenSent- Status. Wenn dies nicht erfolgreich ist, wird der ConnectRetry-Zeitgeber zurückgesetzt und nach Ablauf in den aktiven Zustand versetzt.

Aktiv

Im aktiven Zustand setzt der Router die ConnectRetry Timer auf Null und kehrt in den Connect - Zustand.

OpenSent

Im OpenSent- Status sendet der Router eine Open-Nachricht und wartet auf eine Antwort . Keepalive-Nachrichten werden ausgetauscht, und nach erfolgreichem Empfang wird der Router in den Status " Established" versetzt .

Etabliert

Im eingerichteten Zustand kann der Router senden / empfangen: Keepalive; Aktualisieren; und Benachrichtigungsnachrichten an / von seinem Partner.

Weitere Informationen zu BGP finden Sie auf Wikipedia

Sie sind nützlich, um alle möglichen Dinge zu modellieren. Zum Beispiel kann ein Wahlzyklus mit Staaten nach dem Vorbild von (normale Regierung) - Wahl genannt -> (frühe Wahlkampagne) - Parlament aufgelöst -> (schwere Wahlkampagne) - Wahl -> (Stimmenzählung) modelliert werden ). Dann entweder (Stimmenzählung) - keine Mehrheit -> (Koalitionsverhandlungen) - Einigung erzielt -> (normale Regierung) oder (Stimmenzählung) - Mehrheit -> (normale Regierung). Ich habe eine Variante dieses Schemas in einem Spiel mit einem politischen Teilspiel implementiert.

Sie werden auch in anderen Aspekten von Spielen verwendet: Die KI basiert oft auf dem Status; Übergänge zwischen Menüs und Ebenen und Übergänge nach dem Tod oder abgeschlossener Ebene werden häufig von FSMs gut modelliert.

Der im jquery-csv- Plug-in verwendete CSV-Parser

Es ist ein grundlegender Chomsky- Typ-III-Grammatikparser .

Mit einem Regex-Tokenizer werden die Daten char-by-char ausgewertet. Wenn ein Steuerzeichen angetroffen wird, wird der Code zur weiteren Auswertung basierend auf dem Startzustand an eine switch-Anweisung übergeben. Nicht-Steuerzeichen werden gruppiert und massenweise kopiert, um die Anzahl der erforderlichen Zeichenfolgenkopiervorgänge zu verringern.

Der Tokenizer:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

Die erste Gruppe von Übereinstimmungen besteht aus den Steuerzeichen: Wertbegrenzer ("), Werttrennzeichen (,) und Eingabetrennzeichen (alle Variationen von Zeilenvorschub). Die letzte Übereinstimmung behandelt die Nicht-Steuerzeichen-Gruppierung.

Es gibt 10 Regeln, die der Parser erfüllen muss:

• Regel 1 - Ein Eintrag pro Zeile, jede Zeile endet mit einem Zeilenumbruch
• Regel 2 - Zeilenumbruch am Ende der Datei weggelassen
• Regel 3 - Die erste Zeile enthält Kopfdaten
• Regel 4 - Leerzeichen werden als Daten betrachtet und Einträge sollten kein nachstehendes Komma enthalten
• Regel 5 - Zeilen können durch doppelte Anführungszeichen getrennt sein oder nicht
• Regel 6 - Felder mit Zeilenumbrüchen, Anführungszeichen und Kommas sollten in Anführungszeichen eingeschlossen werden
• Regel Nr. 7 - Wenn Felder in Anführungszeichen gesetzt werden, muss ein Anführungszeichen, das in einem Feld steht, durch ein weiteres Anführungszeichen ersetzt werden
• Änderungsantrag Nr. 1 - Ein nicht zitiertes Feld darf oder darf
• Änderung Nr. 2 - Ein angegebenes Feld kann oder kann nicht
• Änderung Nr. 3 - Das letzte Feld in einem Eintrag kann einen Nullwert enthalten oder nicht

Hinweis: Die Top-7-Regeln sind direkt von IETF RFC 4180 abgeleitet . Die letzten drei wurden hinzugefügt, um Randfälle abzudecken, die von modernen Tabellenkalkulationsanwendungen (z. B. Excel, Google Spreadsheet) eingeführt wurden, bei denen standardmäßig nicht alle Werte eingegrenzt (dh in Anführungszeichen gesetzt) ​​werden. Ich habe versucht, die Änderungen in den RFC einzubringen, habe aber noch keine Antwort auf meine Anfrage erhalten.

Genug mit dem Aufziehen, hier ist das Diagramm:

Zustände:

1. Ausgangszustand für einen Eintrag und / oder einen Wert
2. Ein Eröffnungszitat wurde gefunden
3. Ein zweites Zitat wurde gefunden
4. Es wurde ein Wert ohne Anführungszeichen festgestellt

Übergänge:

• ein. Überprüft, ob sowohl Werte in Anführungszeichen (1) als auch nicht in Anführungszeichen (3), Nullwerte (0), Nulleinträge (0) und neue Einträge (0) vorhanden sind.
• b. sucht nach einem zweiten Anführungszeichen (2)
• c. sucht nach einem maskierten Anführungszeichen (1), dem Ende des Werts (0) und dem Ende der Eingabe (0)
• d. prüft das Ende des Wertes (0) und das Ende der Eingabe (0)

Hinweis: Es fehlt tatsächlich ein Bundesstaat. Es sollte eine Zeile von 'c' -> 'b' sein, die mit dem Status '1' markiert ist, da ein maskierter zweiter Begrenzer bedeutet, dass der erste Begrenzer noch offen ist. In der Tat wäre es wahrscheinlich besser, es als einen weiteren Übergang darzustellen. Diese zu erschaffen ist eine Kunst, es gibt keinen einzigen richtigen Weg.

Hinweis: Es fehlt auch ein Beendigungsstatus, aber bei gültigen Daten endet der Parser immer beim Übergang 'a', und keiner der Status ist möglich, da nichts mehr zum Analysieren übrig ist.

Der Unterschied zwischen Zuständen und Übergängen:

Ein Staat ist endlich, was bedeutet, dass er nur eine Sache bedeuten kann.

Ein Übergang stellt den Fluss zwischen Zuständen dar, sodass er viele Dinge bedeuten kann.

Grundsätzlich ist die Beziehung zwischen Zustand und Übergang 1 -> * (dh Eins-zu-Viele). Der Zustand definiert 'was es ist' und der Übergang definiert 'wie es gehandhabt wird'.

Hinweis: Machen Sie sich keine Sorgen, wenn sich die Anwendung von Zuständen / Übergängen nicht intuitiv anfühlt, sondern nicht intuitiv ist. Es dauerte einige umfangreiche Korrespondenz mit jemandem viel schlauer als ich, bevor ich endlich das Konzept bekam, zu bleiben.

Der Pseudo-Code:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Hinweis: Dies ist das Wesentliche, in der Praxis gibt es noch viel mehr zu beachten. Zum Beispiel Fehlerprüfung, Nullwerte, eine nachgestellte Leerzeile (dh welche ist gültig) usw.

In diesem Fall ist der Zustand der Zustand der Dinge, wenn der reguläre Übereinstimmungsblock eine Iteration beendet. Der Übergang wird als case-Anweisung dargestellt.

Als Menschen haben wir eine Tendenz niedrige Niveaus Operationen in höherer Ebene Abstracts zu vereinfachen , aber die Arbeit mit einem FSM ist die Arbeit mit niedrigem Level - Operationen. Während Zustände und Übergänge sehr einfach einzeln zu bearbeiten sind, ist es von Natur aus schwierig, das Ganze auf einmal zu visualisieren. Ich fand es am einfachsten, den einzelnen Ausführungspfaden immer wieder zu folgen, bis ich verstehen konnte, wie sich die Übergänge abspielen. Es ist wie das Erlernen von Grundlagen der Mathematik, Sie werden nicht in der Lage sein, den Code von einer höheren Ebene aus zu bewerten, bis die Details auf niedriger Ebene automatisch werden.

Nebenbei: Wenn Sie sich die tatsächliche Implementierung ansehen, fehlen viele Details. Erstens lösen alle unmöglichen Pfade bestimmte Ausnahmen aus. Es sollte unmöglich sein, sie zu treffen, aber wenn etwas kaputt geht, lösen sie im Testläufer absolut Ausnahmen aus. Zweitens sind die Parserregeln für das, was in einer "legalen" CSV-Datenzeichenfolge zulässig ist, ziemlich locker, sodass der Code für viele bestimmte Randfälle erforderlich ist. Unabhängig davon wurde der FSM auf diese Weise vor allen Fehlerkorrekturen, Erweiterungen und Feinabstimmungen verspottet.

Wie bei den meisten Designs handelt es sich nicht um eine exakte Darstellung der Implementierung, sondern um die wichtigsten Teile. In der Praxis gibt es tatsächlich drei verschiedene Parserfunktionen, die von diesem Entwurf abgeleitet sind: einen CSV-spezifischen Zeilensplitter, einen einzeiligen Parser und einen vollständigen mehrzeiligen Parser. Sie arbeiten alle auf ähnliche Weise und unterscheiden sich im Umgang mit Zeilenumbrüchen.

Einfaches FSM in Java

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Es geht los. OK, es ist nicht genial, aber es zeigt die Idee.

FSMs finden Sie häufig in Telekommunikationsprodukten, da sie eine einfache Lösung für eine ansonsten komplexe Situation bieten.

Ich habe festgestellt, dass das Nachdenken / Modellieren eines Aufzugs ein gutes Beispiel für eine Zustandsmaschine ist. Es erfordert wenig Einführungsaufwand, bietet aber eine alles andere als triviale Situation zur Umsetzung.

Die Zustände befinden sich beispielsweise im Erdgeschoss, im ersten Stock usw. und bewegen sich von Boden zu Boden oder von Drittel zu Boden, aber derzeit zwischen Etage 3 und 2 und so weiter.

Die Wirkung von Tasten in der Aufzugskabine und auf den Etagen selbst liefert Eingaben, deren Wirkung sowohl von der Taste abhängt, die zusammen mit dem aktuellen Zustand gedrückt wird.

Jede Etage mit Ausnahme der oberen und unteren Etage verfügt über zwei Tasten: eine zum Auffordern des Aufstiegs und die andere zum Abstieg.

OK, hier ist ein Beispiel. Angenommen, Sie möchten eine Ganzzahl analysieren. Es würde so etwas wie dd*wo dist eine ganze Zahl.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Natürlich könnten Sie, wie @Gary sagte, diese gotos mit einer switch-Anweisung und einer state-Variablen verschleiern . Beachten Sie, dass dieser Code so strukturiert werden kann, dass er isomorph zum ursprünglichen regulären Ausdruck ist:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Natürlich können Sie dies auch mit einer Nachschlagetabelle tun.

Finite-State-Maschinen können auf viele Arten hergestellt werden, und viele Dinge können als Instanzen von Finite-State-Maschinen beschrieben werden. Es ist weniger ein "Ding" als vielmehr ein Konzept, um über Dinge nachzudenken.

Beispiel für ein Eisenbahnnetz

Ein Beispiel für eine FSM ist ein Eisenbahnnetz.

Es gibt eine begrenzte Anzahl von Weichen, in denen ein Zug auf eines von zwei Gleisen fahren kann.

Es gibt eine begrenzte Anzahl von Spuren, die diese Schalter verbinden.

Befindet sich ein Zug auf einer Spur, kann er durch Überqueren einer Weiche auf der Grundlage einer einzelnen eingegebenen Information zu einer anderen Spur gesendet werden.

Finite State Machine in Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

Dies ist das Verhalten eines einzelnen Rechenknotens in einem verteilten System, der ein verbindungsbasiertes Kommunikationsschema einrichtet. Mehr oder weniger. In grafischer Form sieht es ungefähr so ​​aus:

Unter diesem Link finden Sie einige einfache Beispiele für die lexikalische Analyse (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Sie können sich auch das "Drachenbuch" ansehen (es ist keine leichte Lektüre)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

In der Praxis werden Zustandsautomaten häufig eingesetzt für:

• Entwurfszwecke (Modellierung der verschiedenen Aktionen in einem Programm)
• Parser für natürliche Sprache (Grammatik)
• String-Analyse

Ein Beispiel wäre eine Zustandsmaschine, die eine Zeichenfolge durchsucht, um festzustellen, ob sie die richtige Syntax hat. Niederländische Postleitzahlen sind beispielsweise als "1234 AB" formatiert. Der erste Teil darf nur Zahlen enthalten, der zweite nur Buchstaben. Es könnte eine Zustandsmaschine geschrieben werden, die protokolliert, ob sie sich im Zustand NUMBER oder im Zustand LETTER befindet, und wenn sie auf eine falsche Eingabe stößt, lehnen Sie sie ab.

Diese Akzeptor-Zustandsmaschine hat zwei Zustände: numerisch und alpha. Die Zustandsmaschine startet im numerischen Zustand und beginnt, die Zeichen der zu überprüfenden Zeichenfolge zu lesen. Wenn in einem der Zustände ungültige Zeichen auftreten, gibt die Funktion einen falschen Wert zurück und weist die Eingabe als ungültig zurück.

Python-Code:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Quelle: (Finite-) State Machines in der Praxis