Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
se:automatentheorie [2008-12-01 14:45] stefan |
se:automatentheorie [2008-12-01 15:10] stefan |
||
---|---|---|---|
Zeile 31: | Zeile 31: | ||
* δ<sup>*</sup>(s, x<sub>i</sub>) = δ(s, x<sub>i</sub>) | x<sub>i</sub> ∈ X, **ein** Zeichen | * δ<sup>*</sup>(s, x<sub>i</sub>) = δ(s, x<sub>i</sub>) | x<sub>i</sub> ∈ X, **ein** Zeichen | ||
* δ<sup>*</sup>(s, x) = δ<sup>*</sup>(s, x<sub>1</sub>x<sub>2</sub>...x<sub>n</sub>) = δ<sup>*</sup>(δ(s, x<sub>1</sub>), x<sub>2</sub>x<sub>3</sub>...x<sub>n</sub>) | * δ<sup>*</sup>(s, x) = δ<sup>*</sup>(s, x<sub>1</sub>x<sub>2</sub>...x<sub>n</sub>) = δ<sup>*</sup>(δ(s, x<sub>1</sub>), x<sub>2</sub>x<sub>3</sub>...x<sub>n</sub>) | ||
+ | * Im DEA gibt es **für jeden Zustand für jedes Eingabezeichen eine Transition** in seinen Folgezustand! | ||
+ | |||
+ | ==== Sprache eines DEA ==== | ||
+ | * L(A) := { w ∈ X<sup>*</sup> | δ<sup>*</sup>(s<sub>0</sub>, 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, S<sub>0</sub>, δ, F) | ||
+ | * X: Eingabealphabet | ||
+ | * S: Zustandsmenge | ||
+ | * S<sub>0</sub>: Menge der Anfangszustände, S<sub>0</sub> ⊆ S | ||
+ | * δ: Zustandsübergangsfunktion | ||
+ | * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | ||
+ | * δ(s<sub>i</sub>, x<sub>j</sub>) → S<sub>k</sub> (Folgezustände zu s<sub>i</sub>, 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, S<sub>0</sub>, δ, F) → A<sup>d</sup> = (X, S<sup>d</sup>, s<sub>0</sub><sup>d</sup>, δ<sup>d</sup>, F<sup>d</sup>) | ||
+ | * S<sup>d</sup> := P(S) (alle möglichen Teilmengen von S) | ||
+ | * s<sub>0</sub><sup>d</sup> := S<sub>0</sub> (Menge der Anfangszustände des NEA ist **ein** Element von P(S)) | ||
+ | * δ(Q, x) := U<sub>q ∈ Q</sub>δ(q, x) | ||
+ | * F<sup>d</sup> := { Q ∈ S<sup>d</sup> | Q ∩ F ≠ ∅} | ||
+ | |||
+ | ===== Pumping-Lemma ===== | ||
+ | * Sei L regulär über X: ∃ n ∈ N, sodass ∀ x ∈ L mit |x| ≥ n: x = uvw (uvw = Teilwörter, u = Weg in den Zyklus, v = Zyklus, w = Weg aus dem Zyklus) | ||
+ | * Bedingung: |uv| ≤ n, |v| ≥ 1, n muss mindestens die Anzahl der Zustände sein | ||
+ | * => uv<sup>i</sup>w ∈ L ∀ i ∈ N (v<sup>i</sup>: v wird i-mal vervielfältigt) | ||
===== ToDo ===== | ===== ToDo ===== | ||
* Skript Herold lesen | * Skript Herold lesen | ||