Feld von Zuständen

Ein endlicher Automat $A$ ist ein 5-Tupel $A=(S, {\Sigma} , {\delta} , s_{0}, F)$ mit

$S$	$=$	endliche Zustandsmenge
${\Sigma}$	$=$	endliches Eingabealphabet
${\delta} : S \times {\Sigma} \rightarrow S$	$=$	Überführungsfunktion
$s_{0} \in S$	$=$	Anfangs- oder Startzustand
$F \subseteq S$	$=$	Endzustände

Ein Wort $w~\in \Sigma^{*}$ wird akzeptiert, falls

$\delta^{*}(s_{0},w) \in F$
$\delta^{*}(s_{0}, x_{0}x_{1}x_{2}\ldots x_{k})={\delta} (\ldots {\delta} ({\delta} ({\delta} (s_{0}, x_{0}), x_{1}),x_{2})\ldots x_{k})$.

Die Wirkungsweise der Überführungsfunktion ${\delta}$ 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: ${\delta} (a, x) = b$.