Endliche Automaten

Leonardo Da Vinci Flying Machine Ein endlicher Automat (englisch "Finite State Machine", FSM oder "Finite State Automaton, FSA) oder Zustandsautomat ist ein System mit einem endlichen Eingabealphabet, einer endlichen Zustandsmenge (inklusive Anfangszustand und Endzustände) und einer Zustandsübergabefunktion.
Die Zustandsübergabefunktion hat den aktuellen Zustand und eine "Eingabe" als Argumente und liefert einen neuen Zustand.
Wenigstens ein Zustand muss ein Endzustand sein.

Der endliche Automat beginnt mit einem besonderen Zustand, dem sogenannten Anfangszustand (oder Startzustand). Normalerweise endet der FSM in einem Endzustand.

Mathematisches Modell:
Ein deterministischer endlicher Automat ist ein Quintupel:
(Σ,S,s0,δ,F),
mit:
einem Eingabealphabet Σ (eine endliche nichtleere Menge von Symbolen)
einer endlichen nicht-leeren Menge S von Zuständen
s0 bezeichnet den Anfangszustand, s0 ∈ S
δ ist die Zustandsübergangsfunktion: δ : S x Σ → S
(in einem nicht-deterministischen endlichen Automaten sieht die Zustandsübergangsfunktion wie folgt aus:
δ : S x Σ → ℘(S), d.h. δ bildet in the Potenzmenge der Zustände ab.
F ist die Menge der Endzustände, F ist eine (möglicherweise leere) Teilmenge von S.

Ein einfaches Beispiel
Wir wollen die Bedeutung von sehr kleinen Sätzen in Englisch mit einem extrem begrenzten Vokabular und einer extrem beschränkten Syntax erkennen:
Diese Sätze sollen mit "Python is" starten und von

Die Adjektive stammen aus einer vordefinierten Menge von Adjektiven. z.B.:
"Python is great" → positive Bedeutung
"Python is stupid" → negative Bedeutung
"Python is not ugly" → positive Bedeutung

Ein endlicher Automat in Python

Um das vorige Beispiel zu implementieren, schreiben wir einen allgemeinen endlichen Automaten in Python. Wir speichern diese Klasse als statemachine.py: 
class StateMachine:
    def __init__(self):
        self.handlers = {}
        self.startState = None
        self.endStates = []

    def add_state(self, name, handler, end_state=0):
        name = name.upper()
        self.handlers[name] = handler
        if end_state:
            self.endStates.append(name)

    def set_start(self, name):
        self.startState = name.upper()

    def run(self, cargo):
        try:
            handler = self.handlers[self.startState]
        except:
            raise InitializationError("must call .set_start() before .run()")
        if not self.endStates:
            raise  InitializationError("at least one state must be an end_state")
    
        while True:
            (newState, cargo) = handler(cargo)
            if newState.upper() in self.endStates:
                print("reached ", newState)
                break 
            else:
                handler = self.handlers[newState.upper()]
Dieser allgemeine endliche Automat wird im folgenden benutzt: 
from statemachine import StateMachine

positive_adjectives = ["great","super", "fun", "entertaining", "easy"]
negative_adjectives = ["boring", "difficult", "ugly", "bad"]

def start_transitions(txt):
    splitted_txt = txt.split(None,1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt,"")
    if word == "Python":
        newState = "Python_state"
    else:
        newState = "error_state"
    return (newState, txt)

def python_state_transitions(txt):
    splitted_txt = txt.split(None,1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt,"")
    if word == "is":
        newState = "is_state"
    else:
        newState = "error_state"
    return (newState, txt)

def is_state_transitions(txt):
    splitted_txt = txt.split(None,1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt,"")
    if word == "not":
        newState = "not_state"
    elif word in positive_adjectives:
        newState = "pos_state"
    elif word in negative_adjectives:
        newState = "neg_state"
    else:
        newState = "error_state"
    return (newState, txt)

def not_state_transitions(txt):
    splitted_txt = txt.split(None,1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt,"")
    if word in positive_adjectives:
        newState = "neg_state"
    elif word in negative_adjectives:
        newState = "pos_state"
    else:
        newState = "error_state"
    return (newState, txt)

def neg_state(txt):
    print("Hallo")
    return ("neg_state", "")

if __name__== "__main__":
    m = StateMachine()
    m.add_state("Start", start_transitions)
    m.add_state("Python_state", python_state_transitions)
    m.add_state("is_state", is_state_transitions)
    m.add_state("not_state", not_state_transitions)
    m.add_state("neg_state", None, end_state=1)
    m.add_state("pos_state", None, end_state=1)
    m.add_state("error_state", None, end_state=1)
    m.set_start("Start")
    m.run("Python is great")
    m.run("Python is difficult")
    m.run("Perl is ugly")
Wenn wir diese Anwendung unseres endlichen Automaten unter statemachine_test.py abspeichern und mit 
python statemachine_test.py
aufrufen, erhalten wir die folgenden Ergebnisse: 
$ python statemachine_test2.py 
reached  pos_state which is an end state
reached  neg_state which is an end state
reached  error_state which is an end state

Die obige Implementierung eines endlichen Automaten ist auch Python3 kompatibel.