Einen endlichen Automaten kann man sich vorstellen als eine Maschine, die Eingaben entgegennimmt, sich in verschiedenen Zuständen befinden kann und Ausgaben tätigt.

Zunächst befindet sich der Automat in einem Anfangszustand S₀.
Die erste Eingabe veranlasst den Automaten, in einen Folgezustand (z.B. S₁, aber auch S₀ wäre möglich) überzugehen und eine Meldung auszugeben (wobei diese Meldung auch leer sein kann, d.h. es wird dann nichts ausgegeben).
Jede weitere Eingabe bewirkt im Zusammenspiel mit dem aktuellen Zustand den Übergang in einen genau bestimmten Zustand und die Ausgabe einer Meldung.
End-Zustände bewirken, dass der Automat im jeweiligen Zustand bleibt, auch wenn noch weitere Eingaben erfolgen.

Wir betrachten nur "Endliche Automaten", die eine endliche Anzahl von Zuständen besitzen, die nur endlich viele verschiedene Werte als Eingabe akzeptieren und die nur endlich viele verschiedene Meldungen ausgeben.

Der Übergang auf Grund einer Eingabe und eines aktuellen Zustandes in einen Folgezustand und die Ausgabe einer Meldung erfolgt durch eine
Überführungsfunktion (aus Eingabe und Zustand folgt Folgezustand) und eine
Ausgabefunktion (aus Eingabe und Zustand folgt Ausgabe).