Endliche Automaten gehören zu den fundamentalsten Konzepten der theoretischen Informatik – und sie sind praktischer, als ihr akademischer Klang vermuten lässt. Ampelsteuerungen, Getränkeautomaten, Parser, Protokolle und das Verhalten ganzer Benutzeroberflächen lassen sich als Zustandsmaschinen modellieren. Dieser Ratgeber erklärt, was ein endlicher Automat ist, worin sich Mealy- und Moore-Automaten unterscheiden und wie du sie sauber aufbaust.
Was ist ein endlicher Automat?
Ein endlicher Automat (englisch Finite State Machine, FSM) ist ein abstraktes Modell, das sich zu jedem Zeitpunkt in genau einem von endlich vielen Zuständen befindet. Trifft eine Eingabe ein, wechselt der Automat über einen Übergang (Transition) in einen anderen Zustand. Ein Automat besteht im Kern aus:
- Einer Menge von Zuständen – etwa "Ruhe", "Münze eingeworfen", "Getränk ausgegeben".
- Einem Eingabealphabet – die erlaubten Eingabesymbole.
- Einer Übergangsfunktion – sie sagt, welcher Zustand bei welcher Eingabe folgt.
- Einem Startzustand und ggf. Endzuständen.
Solche Modelle baust du grafisch am schnellsten mit dem Automaten-Editor: Du ziehst Zustände auf die Fläche, verbindest sie mit Übergängen und siehst die Zustandstabelle live mitlaufen – am Ende exportierst du das Ergebnis als JSON, SVG, PNG oder LaTeX.
Mealy- vs. Moore-Automat
Bei Automaten mit Ausgabe – also solchen, die nicht nur akzeptieren, sondern auch Signale produzieren – gibt es zwei klassische Modelle, die sich in einem entscheidenden Punkt unterscheiden: wann die Ausgabe entsteht.
Moore-Automat
Beim Moore-Automaten hängt die Ausgabe ausschließlich vom aktuellen Zustand ab. Jeder Zustand trägt seine eigene, feste Ausgabe. Erreichst du einen Zustand, erscheint immer dieselbe Ausgabe, egal über welchen Übergang du hineingekommen bist. Das macht Moore-Automaten leicht nachvollziehbar und gut für Steuerungen geeignet, bei denen ein Zustand einem stabilen Ausgangssignal entspricht (z. B. "Ampel rot").
Mealy-Automat
Beim Mealy-Automaten hängt die Ausgabe vom Zustand und von der Eingabe ab – sie ist also dem Übergang zugeordnet, nicht dem Zustand. Dadurch kann ein Mealy-Automat oft mit weniger Zuständen auskommen und reagiert "schneller", weil die Ausgabe schon beim Übergang erfolgt und nicht erst, wenn der Zielzustand erreicht ist.
Beide Modelle sind gleich mächtig: Jeder Moore-Automat lässt sich in einen Mealy-Automaten umwandeln und umgekehrt. Welches du wählst, ist eine Frage von Lesbarkeit und Anwendung.
Die Zustandstabelle
Neben dem Zustandsdiagramm gibt es die Zustandsübergangstabelle – eine tabellarische Darstellung derselben Information. Die Zeilen sind die Zustände, die Spalten die Eingabesymbole, und jede Zelle nennt den Folgezustand (beim Mealy-Automaten zusätzlich die Ausgabe). Diagramm und Tabelle sind zwei Sichten auf dasselbe Modell: Das Diagramm ist intuitiver, die Tabelle eindeutiger und maschinenlesbarer. Ein guter Editor hält beide automatisch synchron.
DFA vs. NFA
Bei reinen Akzeptoren (Automaten ohne Ausgabe, die nur "akzeptiert / nicht akzeptiert" entscheiden) unterscheidet man zwei Varianten:
- DFA (Deterministischer endlicher Automat): Für jeden Zustand und jedes Eingabesymbol gibt es genau einen Folgezustand. Das Verhalten ist eindeutig.
- NFA (Nichtdeterministischer endlicher Automat): Es kann mehrere oder keinen Folgezustand geben, auch sogenannte Epsilon-Übergänge ohne Eingabe sind erlaubt. NFAs sind kompakter, lassen sich aber immer in einen äquivalenten DFA umwandeln (Potenzmengenkonstruktion).
Wo endliche Automaten im Alltag stecken
- Reguläre Ausdrücke: Jede Regex wird intern in einen endlichen Automaten übersetzt. Wer Regex testen will, nutzt den Regex Match Tester.
- Protokolle: TCP-Verbindungen, Ampelsteuerungen und Aufzugslogik sind klassische Zustandsmaschinen.
- UI-Logik: Moderne Frontends modellieren Komponenten oft als State Machines, um unmögliche Zustände auszuschließen.
- Lexer und Parser: Compiler zerlegen Quelltext mit Automaten in Tokens.
Tipps für den Entwurf
Beginne immer mit dem Startzustand und arbeite dich Eingabe für Eingabe vor. Achte darauf, dass dein Automat vollständig ist – bei einem DFA muss jeder Zustand für jedes Eingabesymbol einen definierten Übergang haben, sonst ist das Verhalten undefiniert. Benenne Zustände sprechend statt nur mit q0, q1, q2, sobald die Maschine größer wird. Und prüfe am Ende, ob unerreichbare Zustände existieren – die kannst du gefahrlos entfernen.
Weitere Werkzeuge für Informatik und Entwicklung findest du gebündelt unter kotsch.tech/webtools.
Häufige Fragen
Wofür brauche ich überhaupt Automaten?
Überall dort, wo ein System eine begrenzte Anzahl klar definierter Zustände durchläuft – von der Ampel bis zur Logik einer App. Sie machen Verhalten beweisbar korrekt und verhindern unmögliche Zustände.
Sind Mealy- und Moore-Automaten gleich stark?
Ja. Sie erkennen und erzeugen dieselben Sprachen und lassen sich verlustfrei ineinander überführen. Der Unterschied liegt nur darin, ob die Ausgabe am Zustand oder am Übergang hängt.
Was ist der Unterschied zwischen Automat und Zustandsmaschine?
Die Begriffe werden meist synonym verwendet. "Endlicher Automat" ist der formale Term aus der theoretischen Informatik, "State Machine" der gebräuchliche Begriff in der Softwareentwicklung.