mathematisches Modell eines diskreten dynamischen Systems.

Die Systemzustände werden dabei als Elemente einer Menge Z, der Zustandsmenge, modelliert. Von ihrer inneren Struktur wird weitgehend abstrahiert. Einige der Zustände werden als Anfangsbzw. Endzustände ausgezeichnet, dort kann ein Systemablauf starten bzw. enden. Die Systemdynamik wird durch eine Übergangsrelation δ dargestellt, die jedem Zustand den bzw. die möglichen Nachfolgezustände zuordnet. Für Systeme, die auf Eingaben reagieren sollen, wird ein Eingabealphabet X angegeben; die Übergangsrelation δ hängt dann auch von der jeweiligen Eingabe ab. Wahlweise kann auch bei jedem Zustandsübergang eine Ausgabe über einem Alphabet Y erzeugt werden, die vom aktuellen Zustand und der Eingabe abhängen kann.

Automaten arbeiten taktweise. Anfangs ist einer der Anfangszustände aktueller Zustand. In jedem Takt wird abhängig von der Eingabe und dem aktuellen Zustand ein neuer aktueller Zustand bestimmt und ggf. eine Ausgabe geschrieben. Stellt die Übergangsrelation mehr als einen Folgezustand zur Verfügung, wird einer dieser Zustände nichtdeterministisch ausgewählt.

Ein Automat ist endlich, wenn Zustandsmenge, Eingabe- und ggf. Ausgabealphabet endlich sind.

Verbreitete Varianten endlicher Automaten sind deterministische endliche Automaten, nichtdeterministische endliche Automaten und sog. Moore-Automaten.

Nichtendliche Automaten sind z. B. Kellerautomaten. Automaten haben sich als Werkzeug zur Analyse formaler Sprachen vorzüglich bewährt.

Automaten lassen sich durch Zustandsgraphen darstellen.