DFA_example_multiplies_of_3.png

Ein deterministischer endlicher Automat (DEA, engl.: deterministic finite automaton) ist ein endlicher Automat, der unter Eingabe eines Zeichens einen eindeutig bestimmten Folgezustand annimmt. Außerdem muss ein DEA jedes Wort über dem betrachteten Alphabet bis zum Ende lesen können, auch jene, die nicht in der zu akzeptierenden Sprache enthalten sind.

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

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

Optimierung

---

Eine Möglichkeit der Optimierung ist die Minimierung der Zustandsmenge. Es ist bewiesen, dass zu jedem deterministischen EA ein äquivalenter minimaler Automat (Äquivalenzklassenautomat) existiert.

Dabei ist die Anzahl der Zustände identisch mit der Anzahl der Äquivalenzklassen der vom EA akzeptierten Sprache unter der Äquivalenzrelation

$u\; \backslash equiv\; v\; \backslash Longleftrightarrow\; \backslash forall\; w\; \backslash in\; \backslash Sigma^\{*\}\; :\; uw\; \backslash in\; L(A\_1)\; \backslash Leftrightarrow\; vw\; \backslash in\; L(A\_1)$

Formalisiert bedeutet das: Sei $A\_1=(Q,\backslash Sigma,\backslash delta,q\_0,F)$ ein deterministischer endlicher Automat. Dann ist $A\_2=(Q\text{'},\backslash Sigma,\backslash delta\text{'},q\text{'}\_0,F\text{'})$ mit

• $Q\text{'}=\backslash Big\backslash \{*\backslash mid\; w\; \backslash in\; \backslash Sigma^*\backslash Big\backslash \}$
• $~q\text{'}\_0=*$
• $~\backslash delta\text{'}(*,a)=*$
• $F\text{'}=\backslash Big\backslash \{*\backslash mid\; u\; \backslash in\; L(A\_1)\backslash Big\backslash \}$

der Äquivalenzklassenautomat zu $A\_1$.

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

Automatentheorie

Deterministic finite state machine | אוטומט סופי דטרמיניסטי | Automa a stati finiti deterministico | 決定性有限オートマトン | Deterministyczny automat skończony