Feld von Zuständen

Ein endlicher Automat A ist ein 5-Tupel A = (S,,, s₀, F) mit

S	=	endliche Zustandsmenge
	=	endliches Eingabealphabet
: S x S	=	Überführungsfunktion
s0 S	=	Anfangs- oder Startzustand
F S	=	Endzustände

Ein Wort w  wird akzeptiert, falls

(s₀, w) F
(s₀, x₀x₁x₂...x_k) = (...(((s₀, x₀), x₁), x₂)...x_k).

Die Wirkungsweise der Überführungsfunktion kann durch einen Zustandsüberführungsgraphen beschrieben werden. In diesem Graphen führt eine mit x beschriftete Kante von Knoten a zu Knoten b, falls gilt: (a, x) = b.