prev up next

Previous: Feld von Indizes Up: Felder Next: Beispiel:

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



Unterabschnitte
prev up next
Previous: Feld von Indizes Up: Felder Next: Beispiel: