Finite State Machine

Eine Finite State Machine (FSM, endlicher Automat) ist ein Berechnungsmodell, das sich zu jedem Zeitpunkt in genau einem von endlich vielen Zuständen befindet und durch Eingaben zwischen Zuständen wechselt. Im KI-Kontext sind FSMs die Grundlage für klassische Dialogsysteme und Spielelogik.

Ein FSM besteht aus: Einer endlichen Menge von Zuständen (States), einem Startzustand, Endzuständen (Accepting States), Eingabesymbolen (Input Alphabet) und Übergangsfunktionen (Transition Rules). Die Berechnung ist deterministisch: Ein Zustand + eine Eingabe → genau ein Folgezustand.

In der KI-Frühgeschichte: FSMs modellierten einfache Verhaltensweisen — Spielfiguren patrouillieren bei „normal", verfolgen bei „Spieler gesichtet", fliehen bei „niedrige Gesundheit." Diese Zustandsautomaten waren die Grundlage der Spiele-KI seit Pac-Man (1980).

In der Sprachverarbeitung: Reguläre Ausdrücke (Regex) sind äquivalent zu FSMs. Morphologische Analyse (Wortformenanalyse) nutzt endliche Transduktoren (erweiterte FSMs). Xerox's Finite-State-Toolkit war in den 1990ern ein Standard-NLP-Tool.

Limitationen: FSMs können keine verschachtelten oder rekursiven Strukturen verarbeiten (z.B. verschachtelte Klammern in natürlicher Sprache). Dafür braucht man Pushdown-Automaten (mit Stack) oder Turing-Maschinen. Die Chomsky-Hierarchie formalisiert diese Grenzen.

In der modernen KI: FSMs sind weitgehend durch ML ersetzt — aber sie bleiben als konzeptuelles Werkzeug und für einfache, deterministische Logik (API-Orchestrierung, Workflow-Steuerung) nützlich. Manche LLM-Agent-Frameworks nutzen FSMs für die Steuerung des Agenten-Workflows.