Endliche Zustandsmaschine erklärt

Die Finite-State-Maschine (FSM) ist ein Software-Entwurfsmuster, bei dem ein bestimmtes Modell durch externe Eingabe in andere Verhaltenszustände übergeht.

Grundlegendes zur Finite-State-Maschine

Ein FSM wird durch seine Zustände , seinen Anfangszustand und die Übergänge definiert .

Die Stärke von FSM beruht auf der Fähigkeit, unterschiedliche Verhaltensweisen unter verschiedenen Bedingungen klar zu definieren . Normalerweise wird FSM mit Schleifverhaltensskripten verwendet, die ständig die aktuelle Situation in einer Schleife oder mit Ereignissen bewerten.

Um ein Bild davon zu erhalten, wie dies angewendet werden könnte, wird eine Kaffeemaschine als Beispiel für eine Finite-State-Maschine verwendet. Wir werden auch ein Zustandsdiagramm behandeln, um das FSM zu visualisieren und Codierungsbeispiele bereitzustellen.

Zustandsdiagramm

Finite-State-Machine-Diagramm der Kaffeemaschine

Dieses Diagramm zeigt drei mögliche Zustände für die Kaffeemaschine:

  • Öffnen
  • ReadyToBuy
  • Ausgeschaltet

Die Linien zwischen diesen Zuständen zeigen, welche Übergänge zwischen Zuständen in welche Richtung möglich sind. Diese Übergänge haben Bedingungen dafür, wann der FSM zwischen Zuständen wechseln muss.

  • StartUpMachine Vom PoweredOff-Status in den Open-Status muss der Computer gestartet werden. Dies erfolgt in diesem Fall manuell.
  • Einzahlung> = Kaffeekosten Der FSM wertet den eingezahlten Bargeldbetrag entweder in einer Schleife oder bei Änderung des Betrags aus (in diesem Fall empfohlen). Wenn Sie genügend Bargeld in die Kaffeemaschine einzahlen, wechselt der FSM von "Öffnen" zu "Bereit" '.
  • ShutdownMachine Die Maschine wechselt automatisch über die ShutDownMachine-Methode von Open zu PoweredOff, wenn die Bedingung "Keine Kaffees mehr übrig" erfüllt ist.
  • DispenseCoffee Im ReadyToBuy-Status kann der Benutzer einen Kaffee kaufen, der anschließend gebrüht und ausgegeben wird. Die Bedingung ist, wenn das BuyCoffee-Ereignis (! Link zum Beobachtermuster!) Ausgelöst wird. (im Diagramm nicht dargestellt)
  • CancelCoffee Wenn der Benutzer abbrechen möchte, wechselt der Computer von ReadyToBuy zu Open.
  • ShutDownMachine Der Computer wechselt in den PoweredOff-Status

Zustände

In jedem Zustand gibt es ein definiertes Verhalten, das nur ausgeführt wird, wenn sich das Objekt in diesem Zustand befindet. Während des PoweredOff-Vorgangs brüht die Kaffeemaschine beispielsweise keinen Kaffee, bevor sie eingeschaltet wird. Im geöffneten Zustand wartet sie entweder, bis genügend Bargeld eingezahlt ist, bis der Ausschaltbefehl erteilt wird oder bis der Kaffee ausgeht. Während dieses geöffneten Zustands können Routinen wie das Reinigen ausgeführt werden, die in anderen Zuständen nicht stattfinden.

Ausgangszustand

Jeder FSM hat einen Anfangszustand. Dies bedeutet, in welchem ​​Zustand er beim Erstellen beginnt und beim Erstellen oder Instanziieren definiert werden muss. Natürlich ist es möglich, den Status direkt zu ändern, wenn die Bedingungen erfüllt sind.

Übergänge

Jeder Zustand bewertet entweder ständig, ob er in einen anderen Zustand übergehen soll, oder er wechselt basierend auf einem ausgelösten Ereignis in einen anderen Zustand.

DFA und NFA

Es gibt zwei Arten von endlichen Automaten: Deterministisch (DFA) und Nichtdeterministisch (NFA). Beide akzeptieren reguläre Sprachen und arbeiten mehr oder weniger auf die oben beschriebene Weise, jedoch mit einigen Unterschieden.

Ein DFA akzeptiert oder lehnt eine Zeichenfolge ab und erzeugt nur eine eindeutige Berechnung oder einen eindeutigen Automaten für jede Eingabezeichenfolge. Deterministisch bezieht sich auf die Eindeutigkeit der Berechnung. Eine Finite-State-Maschine wird als DFA bezeichnet, wenn sie die folgenden Regeln befolgt:

  1. Jeder seiner Übergänge wird eindeutig durch seinen Quellzustand und sein Eingabesymbol bestimmt
  2. Das Lesen eines Eingabesymbols ist für jeden Zustandsübergang erforderlich.

Ein NFA muss diese Einschränkungen nicht einhalten, was bedeutet, dass jeder DFA auch ein NFA ist. Und da beide nur reguläre Sprachen erkennen, kann jeder NFA mithilfe des Powerset-Konstruktionsalgorithmus in einen äquivalenten DFA konvertiert werden.

Welche Regeln können wir also in NFAs erwarten, aber nicht in DFAs?

  1. Ein NFA kann einen leeren Zeichenfolgenübergang haben (im Allgemeinen durch ein Epsilon gekennzeichnet). Dies bedeutet, dass die Maschine in einem bestimmten Zustand mit einem Epsilon für eine Übergangsregel in den nächsten Zustand übergehen kann, ohne ein Eingabesymbol zu lesen
  2. In einer NFA kann jedes Paar von Status und Übergangssymbol mehrere Zielzustände haben, im Gegensatz zu den eindeutigen Zielen von Paaren in DFAs
  3. Jedes Paar von Zustands- und Übergangssymbolen erzeugt einen 'Zweig' der Berechnung für jedes seiner möglichen Ziele, wodurch eine Art Multithread-System entsteht.
  4. Ein DFA lehnt die Eingabezeichenfolge ab, wenn er in einem anderen Status als dem Akzeptanzstatus landet. In einer NFA benötigen wir nur einen 'Zweig', um in einem Akzeptanzzustand zu landen, um die Zeichenfolge zu akzeptieren.

Wenn Sie mehr erfahren möchten, finden Sie hier eine ausführliche Anleitung zu Zustandsautomaten.