Zustandsmaschinen

Zustandsmaschinen, auch Zustandsautomaten, sind abstrakte Modelle der Berechnung, die aus einer endlichen Menge von Zuständen bestehen und durch Übergänge zwischen diesen Zuständen auf Eingaben reagieren. Sie beschreiben Dynamik durch Folgen von Zuständen, wobei der aktuelle Zustand den Verlauf des Systems codiert.

Wichtige Komponenten: eine Zustandsmenge Q, ein Eingabealphabet Σ, eine Übergangsfunktion δ, ein Startzustand q0 ∈ Q und eine Menge von Endzuständen F ⊆ Q. Eine deterministische endliche Automatik (DFA) hat für jeden Zustand und jedes Symbol genau einen Folgezustand; ein nichtdeterministischer endlicher Automat (NFA) darf mehrere Folgezustände haben und kann ε-Übergänge verwenden. Formal: δ: Q × Σ → Q (DFA) bzw. δ: Q × Σ → P(Q) (NFA).

Ausgabeorientierte Varianten reichen als Mealy- oder Moore-Maschinen, bei denen die Ausgaben an Zustandsübergängen oder Zuständen hängen. Zustandsmaschinen erkennen oder erzeugen Muster, und sie sind äquivalent zu regulären Sprachen: Jeder DFA akzeptiert eine reguläre Sprache, und jede reguläre Sprache lässt sich durch einen DFA akzeptieren.

Anwendungen finden sich in der theoretischen Informatik sowie in der Praxis, z. B. bei Lexikalischen Analysatoren, Parsers, regelbasierten Steuerungen, Protokoll- oder Prozesssteuerung, sowie in digitalen Schaltungen und eingebetteten Systemen.

Beispiele: Ein einfacher Ziffernerkenner, der Eingaben wie 0–9 akzeptiert, oder eine Türschlosslogik, die nach Eingabe einer richtigen Sequenz in den Zielzustand wechselt; eine Ampelsteuerung kann als endlicher Automat modelliert werden, der zwischen Grün, Gelb und Rot wechselt.

Historisch entstanden die Konzepte aus der formalen Sprach- und Automatentheorie, maßgeblich durch Kleene, Rabin–Scott und Chomsky. Heute dienen Zustandsmaschinen als Grundlagenwerkzeug in Theorie und Praxis.