Beispiele für Zustandsautomaten [geschlossen]

25

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.

ocodo
quelle
12
Reguläre Ausdrücke sind Zustandsmaschinen.
Chrisaycock
5
Ich verstehe nicht, warum diese Frage als "nicht konstruktiv" markiert ist. Angesichts der Tatsache, dass es fast 2 Jahre her ist, seit ich zum ersten Mal eine Antwort vorgelegt habe, dass sie geschlossen ist, würde ich argumentieren, dass sie tatsächlich sehr konstruktiv und thematisch war.
Aqua
2
@aqua - es ist wirklich eher ein Problem mit Stack.Programmierer, es ist das Mandat, Fragen zu beantworten, sehr, sehr spezifische Fragen, die eine Antwort haben. Fragen wie diese, die wertvoll sind, werden jedoch nicht als "konstruktiv" (eine sehr schlechte Definition des Begriffs in IMNSHO) auf der Grundlage der Definition von Stapelstandorten im Allgemeinen angesehen. Um ehrlich zu sein, dass Programmierer wirklich nützlich sind, sollte diese Regel weniger eifrig eingehalten werden, aber ich bin alt, müde und anderweitig engagiert, um die erforderlichen Anstrengungen zu unternehmen, um zu versuchen, die Dummheit zu beheben.
ocodo
1
Tatsächlich besteht das eigentliche Problem darin, dass Stack-Sites offen gesagt eine der wenigen hochqualitativen Ressourcen sind, die bekannt und kooperativ sind und ein gutes, lesbares Format haben. Es scheint, dass dieser Reduktionismus auf Stapel wirklich auf eine Notwendigkeit für das Site-Format hinweist, das für pädagogische "Fragen"
gedacht ist
3
Ich würde die Leute immer noch bitten, diese Frage erneut zu eröffnen, denn weitere Beispiele wären großartig. Die traurige Tatsache ist, dass die Frage offen geblieben wäre, wenn keine neuen Antworten hinzugefügt worden wären.
ocodo

Antworten:

28

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)
aqua
quelle
+1 und mehr, wenn ich könnte. Bis auf den letzten sieht alles gut aus. Es sollte IDLE, VEND und CHANGE sein. Die Werte sind bedingt und sollten als Übergang zwischen IDLE und sich selbst dargestellt werden. Sie möchten auch einen Status, der angibt, dass ein Element ausgewählt wurde.
Evan Plaice
@EvanPlaice: Wäre die Auswahl eines Elements nicht einfach das Ereignis, das einen Wechsel von IDLE zu VEND auslöst? Es sei denn, Sie stellen sich vor dem Verkauf eine Methode zur Bestätigung der Auswahl vor.
Misko
Gibt es eine Chance für ein Diagramm für diese beiden?
ocodo
Dies sind die gleichen Beispiele wie auf der FSM-Wikipedia-Seite , zu der auch Aufzüge gehören: "Einfache Beispiele sind Verkaufsautomaten , die Produkte ausgeben, wenn die richtige Kombination von Münzen eingeworfen wird, Aufzüge , deren Reihenfolge von den angeforderten Stockwerken abhängt von Fahrern, Ampeln , die die Reihenfolge ändern, wenn Autos warten, und Zahlenschlössern , die die Eingabe von Zahlenkombinationen in der richtigen Reihenfolge erfordern. "
ICC97
1
@ icc97 FSM-Beispiele sind zahlreich und alltäglich. Übrigens datiert der Stapelaustauschposten die Aufnahme der Beispielinformationen auf der Wikipedia-Seite vor :)
aqua
14

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.

BGP-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

ocodo
quelle
@tcrosley - es ist aus Wikipedia, verdient also nicht wirklich Anerkennung.
ocodo
1
ok, +1 für einschließlich eines Diagramms. :)
Tcrosley
Ich habe versucht, die Beschriftung des Diagramms auf BGP zu korrigieren, aber es ließ mich nicht - nicht genug Zeichen :)
Mike Dunlavey
Es muss einen besseren Weg geben, dies zu zeichnen.
Job
1
@Job - etwas verspätete Antwort, sorry, aber ich denke jetzt immer wieder, dass dies ein viel zu esoterisches Beispiel ist. Der Safe, der Verkaufsautomat usw. sind meiner Meinung nach viel nützlicher.
Ocodo
7

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.

Peter Taylor
quelle
++ Nettes Beispiel.
Mike Dunlavey
1
+1 Gutes Beispiel für eine DFM (Deterministic Finite State Machine), weil die Pfade.
Evan Plaice
4

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:

CSV-Parser-Zustandsmaschine

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.

Evan Scholle
quelle
1
whoa! sehr netter beitrag.
ocodo
@ Slomojo Danke, ich freue mich zu teilen. Ich ging nicht zur Schule für CS, also musste ich dieses Zeug selbst lernen. Es ist wirklich schwierig, reale Anwendungen zu finden, die solche hochrangigen CS-Themen online abdecken. Ich plane, den Parser-Algorithmus irgendwann detailliert zu dokumentieren, damit er in Zukunft für andere wie mich nützlich sein kann. Das ist ein guter Anfang.
Evan Plaice
Ich bin auch Autodidakt, aber ich habe vor 30 Jahren angefangen, und jetzt habe ich den CS-Lehrplan behandelt :) Ich habe diese Frage für Leute wie Sie und mich gestellt. Ich denke, es war damals bedeutend einfacher, Theorie auf sehr niedrigem Niveau zu lernen, einfach weil es weniger Ablenkung und mehr Möglichkeiten gab, in der Nähe des Metalls zu arbeiten, obwohl es eigentlich kein Internet gab und wir alle in Höhlen lebten.
ocodo
3

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.

Gary Rowe
quelle
3
Sie sind auch ein wichtiger Bestandteil der Compilerkonstruktion in der lexikalischen Analyse.
JMQ
@jmquigley, kannst du bitte eine Antwort hinzufügen?
Ocodo
1
Ich habe eine separate Antwort mit ein paar Links für Sie hinzugefügt.
14.
3

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.

jan
quelle
2

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.

Mike Dunlavey
quelle
(Ich habe Ihre Antwort bearbeitet, ich hoffe, Sie
stimmen
@ Slomojo: Das ist in Ordnung. Sieht gut aus.
Mike Dunlavey
2

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:

Bildbeschreibung hier eingeben

philosodad
quelle
+1 Interessant. Worauf bezieht sich DGMM?
Evan Plaice
@EvanPlaice ist der Distributed Maximum-Matching-basierte Minimum-Weighted Vertex Cover Algorithmus (DGMM) ... ein leicht abgekürztes Akronym, frag mich nicht, woher das G kommt.
ocodo
@slomojo Das "G" steht für "Verallgemeinert", der sequentielle Algorithmus, von dem dieser abgeleitet wird, verwendet eine Technik, die verallgemeinerte maximale Übereinstimmung genannt wird.
Philosodad
@philosodad Ich habe das angenommen, aber ich poste keine Annahmen.
Ocodo
0

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

theD
quelle