Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
se:automatentheorie [2008-12-01 15:04] stefan |
se:automatentheorie [2008-12-01 15:10] stefan |
||
---|---|---|---|
Zeile 54: | Zeile 54: | ||
* δ(Q, x) := U<sub>q ∈ Q</sub>δ(q, x) | * δ(Q, x) := U<sub>q ∈ Q</sub>δ(q, x) | ||
* F<sup>d</sup> := { Q ∈ S<sup>d</sup> | Q ∩ F ≠ ∅} | * 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 | ||