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. e.g.
"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.endStates = []
        self.startState = None

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

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

    def run(self, content):
        if self.startState in self.handlers:
            handler = self.handlers[self.startState]
        else:
            raise "InitializationError", ".set_start() has to be called before .run()"
        if not self.endStates:
            raise  "InitializationError", "at least one state must be an end_state"

        oldState = self.startState
        while 1:
            (newState, content) = handler(content, oldState)
            if newState in self.endStates:
                print "reached ", newState, "which is an end state"
                break 
            else:
                handler = self.handlers[newState]
            oldState = newState
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 transitions(txt, state):
    splitted_txt = txt.split(None,1)
    word, txt = splitted_txt if len(splitted_txt) > 1 else (txt,"")
    if state == "Start":
        if word == "Python":
            newState = "Python_state"
        else:
            newState = "error_state"
        return (newState, txt)
    elif state == "Python_state":
        if word == "is":
            newState = "is_state"
        else:
            newState = "error_state"
        return (newState, txt) 
    elif state == "is_state":
        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)
    elif state == "not_state":
        if word in positive_adjectives:
            newState = "neg_state"
        elif word in negative_adjectives:
            newState = "pos_state"
        else:
            newState = "error_state"
        return (newState, txt)
    

if __name__== "__main__":
    m = StateMachine()
    m.add_state("Start", transitions)
    m.add_state("Python_state", transitions)
    m.add_state("is_state", transitions)
    m.add_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