S | = | endliche Zustandsmenge |
= | endliches Eingabealphabet | |
: S x S | = | Überführungsfunktion |
s0 S | = | Anfangs- oder Startzustand |
F S | = | Endzustände |
(s0, w) FDie 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.
(s0, x0x1x2...xk) = (...(((s0, x0), x1), x2)...xk).