se:automatentheorie
**Dies ist eine alte Version des Dokuments!**
Automatentheorie
Einleitung
Einordung "Automatentheorie"
Funktion endlicher Automaten: Eingaben → (innere) Zustände → Ausgaben
Klassifizierung
Eingaben: Zeichenfolgen über Alphabet X = { x1, x2, …, xn }
Ausgaben: Zeichenfolgen über Alphabet Y = { y1, y2, …, yn }
Zustände (states): unterscheidbare Stadien der Verarbeitung von Eingaben
Zustandsmenge S = { s1, s2, …, sn }
Partizipien weisen auf Zustände hin: "Taste gedrückt" etc.
Deterministische endliche Automaten (DEA)
Definition: A = (X, S, s0, δ, F)
Sprache eines DEA
L(A) := { w ∈ X</sup> | δ*(s0, w) ∈ F} (Menge aller Wörter, die vom Anfangszustand in einen Endzustand führen)
* durch endliche Automaten akzeptierbar/definierbar, falls es einen DEA gibt, der sie akzeptiert
===== Nicht-deterministische endliche Automaten (NEA) =====
* Definition: A = (X, S, S0, δ, F)
* X: Eingabealphabet
* S: Zustandsmenge
* S0: Menge der Anfangszustände, S0 ⊆ S
* δ: Zustandsübergangsfunktion
* S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich
* δ(si, xj) → Sk (Folgezustände zu si, leere Menge, ein oder mehrere Zustände)
==== Überprüfung, ob NEA und DEA äquivalent ====
- Konstruiere zu gegebenem DEA einen äquivalenten NEA (direkt erfüllt, da jeder DEA schon ein NEA ist)
- Konstruiere zu gegebenem NEA einen äquivalenten DEA (akzeptiert die selbe Sprache)
* A = (X, S, S0, δ, F) → Ad = (X, Sd, s0d, δd, Fd)
* Sd := P(S) (alle möglichen Teilmengen von S)
* s0d := S0 (Menge der Anfangszustände des NEA ist ein Element von P(S))
* δ(Q, x) := Uq ∈ Qδ(q, x)
* Fd := { Q ∈ Sd | Q ∩ F ≠ ∅}
===== ToDo =====
* Skript Herold lesen
se/automatentheorie.1228140253.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)