Zustandsautomaten

Zustandsautomaten, auch endliche Automaten genannt, sind abstrakte Rechenmodelle zur Modellierung von Systemen, die auf eine Folge von Eingabezeichen reagieren. Ein Zustandsautomat besteht aus einer endlichen Menge von Zuständen Q, einem Alphabet Σ von Eingabezeichen, einer Übergangsfunktion δ, einem Startzustand q0 ∈ Q und einer Teilmenge F ⊆ Q von akzeptierenden Zuständen. Die Übergangsfunktion beschreibt, wie das aktuelle Zustand anhand des gelesenen Symbols in einen nächsten Zustand übergeht. Ein Wort wird akzeptiert, wenn der Automat nach der Verarbeitung des Wortes in einem Zustand aus F landet.

In einem deterministischen endlichen Automaten (DFA) besitzt jeder Zustand und jedes Eingabezeichen genau einen Folgezustand. In einem nichtdeterministischen endlichen Automaten (NFA) kann es mehrere Folgezustände geben; oft werden auch ε-Übergänge verwendet, die ohne Eingabe ein weiteres Stadium ermöglichen. Jedes NFA kann in äquivalenten DFA überführt werden (Subset-Konstruktion).

Die von endlichen Automaten erkannten Sprachen heißen reguläre Sprachen. Sie besitzen geschlossene Eigenschaften unter Vereinigung, Konkatenation, Kleene-Stern und Spiegelung, und es gibt Techniken zur Minimierung von Automaten, um eine Automatisierung mit minimaler Zustandsanzahl zu finden.

Zustandsautomaten finden breite Anwendung in der Informatik: In der Lexikalischen Analyse von Compilern, in der Mustererkennung und Textverarbeitung, in der Modellprüfung und Verifikation sowie im Hardwaredesign. Sie bilden zudem die theoretische Grundlage für weitergehende Modelle der Berechnung, etwa für reguläre Ausdrücke und Sprachmaschinen.