Deterministischer endlicher Automat

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Ein deterministischer endlicher Automat (DEA, engl.: DFA=deterministic finite automaton) ist ein endlicher Automat, der unter Eingabe eines Zeichens einen eindeutig bestimmten Folgezustand annimmt. Ist ein DEA in der Lage jedes Wort über dem betrachteten Alphabet bis zum Ende lesen zu können, auch wenn es nicht in der zu akzeptierenden Sprache enthalten ist, wird er Vollstaendig genannt

Formal kann ein DEA $\mathcal{A}$ als 5-Tupel $\left( Q, \Sigma, \delta, q_0, F \right)$ definiert werden. Hierbei gilt Folgendes:

$Q$ ist eine nichtleere endliche Menge von Zuständen. Statt $Q$ wird oft auch $Z$ oder $S$ verwendet.
$Σ$ ist ein endliches Eingabealphabet.
Es gibt eine Übergangsfunktion $\delta : Q \times \Sigma \rightarrow Q$ , $δ(q, a) = p$ mit $q, p \in Q$ , $a \in \Sigma$ , die jedem Paar, bestehend aus einem Zustand $q$ und einem Eingabesymbol $a$ , einen neuen Zustand $p$ zuordnet. Weniger formal: Man kommt von $q$ nach $p$ , wenn man in $q$ ein $a$ eingibt.
$q_0 \in Q$ ist der Startzustand. Statt $q 0$ wird oft auch $z 0$ verwendet.
$F \subseteq Q$ ist die Menge der akzeptierenden Zustände, die sogenannte Endzustandsmenge. Wenn der Automat nach dem Lesen des Eingabewortes $w \in \Sigma^*$ in einem Zustand aus $F$ hält, so gehört w zur Sprache $L\left(A\right)$ . Statt $F$ wird oft auch $A$ verwendet.

Nichtdeterministische endliche Automaten (NEAs), DEAs und Typ-3-Grammatiken (vgl. Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs wandeln.

[Bearbeiten] Minimierung

Zu jedem DEA existiert ein eindeutiger minimaler Automat, der die gleiche Sprache akzeptiert.

Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten $M$ akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:

$u \sim_{L(M)} v \Longleftrightarrow \forall w \in \Sigma^{*} : uw \in L(M) \Leftrightarrow vw \in L(M)$

Sei $M = (Q,Σ,δ, q 0, F)$ ein deterministischer endlicher Automat. Dann ist $N = (Q',Σ,δ', q' 0, F')$ mit

$Q'=\Big\{[w]_{L(M)} \mid w \in \Sigma^*\Big\}$
$~q'_0=[\epsilon]_{L(M)}$
$~\delta'([u]_{L(M)} ,a)=[ua]_{L(M)}$
$F'=\Big\{[u]_{L(M)} \mid u \in L(M)\Big\}$

der Äquivalenzklassenautomat zu $M$ .

Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen $F$ und $Q / F$ . Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet. Dies wird so oft wiederholt bis sich keine Änderung mehr ergibt.

[Bearbeiten] Literatur

John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage. Pearson Studium, Reading 2002, ISBN 3-8273-7020-5
Gottfried Vossen, Kurt-Ulrich Witt, Grundkurs Theoretische Informatik 3.Auflage, ISBN 3-528-23147-5
Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5
Uwe Schöning: Ideen der Informatik, Grundlegende Modelle und Konzepte. Oldenbourg, München 2006, ISBN 3-486-57833-2

Von „http://de.wikipedia.org../../../d/e/t/Deterministischer_endlicher_Automat_041c.html“

Kategorie: Automatentheorie

Deterministischer endlicher Automat

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] Minimierung

[Bearbeiten] Literatur

Views

Navigation

Mitmachen

Suche

Andere Sprachen