Feld von Zuständen

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

S = endliche Zustandsmenge

= endliches Eingabealphabet

= Überführungsfunktion

= Anfangs- oder Startzustand

= 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 .