Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

Zurück zu 10.04.2007

Hoch zu Inhaltsverzeichnis

Vor zu 19.04.2007

Handschriftliche Version

Inhaltsverzeichnis

1 Endliche Automaten

Endliche Automaten

Der Automat

Es gibt 3 Typen endlicher Automaten

* deterministische endliche Automaten (DEA)
* nichtdet. endl. Automaten (NEA)
* nichtdet. endl. Automaten mit spontanen Übergängen ( $ε$ -NEA)

Beispiel eines Automaten (hier ein NEA):

Erläuterung:

Ist der Startzustand, gekennzeichnet durch einen losen Pfeil

Ist der Endzustand, gekennzeichnet durch den doppelten Kreis

Ist eine Transition, ein Übergang von einem in den anderen Zustand. $a \in \Sigma$

Funktionsweise

Sei

ein Eingabeband.

Initial steht der Eingabewert auf dem Eingabeband
Schritt:

   * 1. lese nächstes Eingabesymbol (am Lesekopf)
   * 2. wechsle Zustand entspr. der endl. Kontrolle
   * 3. verschiebe den Lesekopf eine Position weiter

halte die Berechnung an, sobald das letzte Zeichen der Eingabe gelesen ist. Akzeptiere das Eingabewort, falls der letzte Zustand ein Endzustand ist.

Definition: Deterministischer Endlicher Automat (DEA)

Ein DEA ist ein Quintupel $M=(\mathbb Q,\Sigma, \delta, q_{0}, \mathbb F)$ , wobei

$\mathbb Q$ eine endliche Menge von Zuständen ist
$Σ$ ein endliches Alphabet ist
$\delta:\mathbb Q\times\Sigma\rightarrow\mathbb Q$ eine partielle Funktion (Übergangsfunktion) ist
$q_{0}\in\mathbb Q$ ein Startzustand ist
$\mathbb F\subseteq\mathbb Q$ Endzustände

In der englischen Fachliteratur werden diese auch als deterministic finite automaton (DFA) bezeichnet.

Beispiel

$M = (\mathbb Q, \Sigma, \delta, q_{0}, \mathbb F)$
$\mathbb Q = \{q_{0}, q_{1}\}$
$Σ = {a, b}$
$\mathbb F = \{q_{1}\}$

$δ(q 0, a) = q 0$
$δ(q 0, b) = q 1$
$δ(q 1, a) = q 1$
$δ(q 1, b) = q 0$

Übergangsfunktion

$\delta(q_{0}, b) = \perp$ ( $\perp$ =nicht definiert)
$\delta(q_{1}, a) = \perp$

Transformation des Automaten um die undefinierten Übergänge zu eliminieren: füge einen neuen Fangzustand $q F$ hinzu und ersetze alle Transitionen $\delta(q_i, a) = \perp$ durch Transitionen in den Zustand $q F$ . Dann entsteht eine totale Übergangsfunktion.

Hierunter folgt als Beispiel die Transformation des obigen Automaten. $p$ ist der Fangzustand.

Für gewisse Operationen (z. B. Komplement) ist es Voraussetzung, dass $δ$ eine totale Funktion ist.

Definition: Erweiterte Übergangsfunktion

Sei $M=(\mathbb Q,\Sigma,\delta,q_{0},\mathbb F)$ ein DEA. Die erweiterte Übergangsfunktion $\delta :\mathbb Q\times\Sigma^{*}\rightarrow\mathbb Q, \forall a\in\Sigma, x\in\Sigma^{*}$ und $q\in\mathbb Q$ :

$δ(q,ε) = q$
$\delta(q,ax) = \begin{cases} \delta(\delta(q,a),x) \mbox{ falls } \delta(q,a)\neq\perp\\ \perp\mbox{ sonst} \end{cases}$

Definition: Akzeptierte Sprache

Die von M akzeptierte Sprache ist wie folgt definiert:

Beispiel

    $w = b a a b b a b b$ 

   ?

Nun überprüfen wir ob dieses Wort in der Sprache des oben genannten Automaten liegt:

    $δ(q 0, b a a b b a b b) = δ(δ(q 0, b), a a b b a b b)$ 

    $δ(δ(q 0, a), a b b a a b b) = δ(δ(q 0, a), b b a b b)$ 

    $δ(δ(q 0, b), b a a b b) = δ(δ(q 0, b), a b b) = δ(δ(q 0, a), b b)$

Die Sprache ist wie folgt definiert:

Für DEA gilt

Zu jedem Eingabewort gehört genau ein Lauf

Satz

Zu jedem DEA M gibt es eine reguläre Grammatik G, sodass L(M)=L(G)

Beweisvorbereitung

Sei $M=(\mathbb Q, \Sigma, \delta, q_{0},\mathbb F)$ ein DEA, wobei $δ$ total ist.
Idee: Zustände werden aufgefasst als Nichtterminalsymbole und die Übergangsfunktion definiert Produktionsregel.

   Sei  $G = (V,Σ, P, S)$  wobei  $V = Q$    $S = q 0$

P ist wie folgt definiert:

Ist $q_{0}\in\mathbb F$ dann $q_{0}\rightarrow\epsilon$
Ist $δ(q, a) = p$ dann $q\rightarrow ap$
Ist $\delta(q,a)=p\in\mathbb F$ dann $q\rightarrow a$

Beweis

Klar: G ist regulär

Jetzt bleibt zu beweisen dass $L (G) = L (M)$

" $\supseteq$ "

Sei $x=a_{1}\cdots a_{n}\in\Sigma^{*}$ und $q_{0}q_{1}\cdots q_{n}$ der zu x gehörende Lauf in M.
Sei $x\in L(M)$ . Somit ist $q_{0}q_{1}\cdots q_{n}$ ein akzeptierender Lauf, d.h. $q_{n}\in\mathbb F$ .

Aber dann