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_{n-1})={\delta} (\ldots {\delta} ({\delta} ({\delta} (s_{0}, x_{0}), x_{1}),x_{2})\ldots x_{n-1})$.

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 $s$ zu Knoten $t$, falls gilt: ${\delta} (s, x) = t$.

Beispiel: $A$ soll durch $3$ teilbare Dualzahlen erkennen. Hierzu spendieren wir drei Zustände mit der Bedeutung Rest 0, Rest 1 und Rest 2. Folgende Fälle können auftreten, wenn ein String $w$, dessen Rest als 0, 1 oder 2 bekannt ist, verlängert wird mit dem Zeichen 0 bzw. mit dem Zeichen 1:

w	w0	w1
3x + 0	6x + 0	6x + 1
Rest 0	Rest 0	Rest 1
3x + 1	6x + 2	6x + 3
Rest 1	Rest 2	Rest 0
3x + 2	6x + 4	6x + 5
Rest 2	Rest 1	Rest 2

Also ergibt sich folgender Automat:

$S = \{ r_{0}, r_{1}, r_{2} \}$
$\Sigma = \{\mbox{\tt '0', '1'}\}$
Startzustand ist $r_{0}$
$F=\{ r_{0}\}$

Dazu gehört ein Zustandsüberführungsgraph mit den Knoten $r_0$, $r_1$ und $r_2$, welche die Zustände beschreiben, wenn für den bislang eingelesenen String die Division durch 3 den Rest 0, 1 bzw. 2 ergibt. An der Kante steht das jeweils nächste Bit der Dualzahl, die von links nach rechts abgearbeitet wird.

Source: Automat.java     JavaDoc: Automat.html     Applet: