prev up next

Previous: Feld von Indizes Up: Felder Next: Lineare und binäre Suche

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:


prev up next
Previous: Feld von Indizes Up: Felder Next: Lineare und binäre Suche