Wie wendet man das Pumping-Lemma an?
Hallo weiß jemand wie man hier das Pumping Lemma anwedet ?
Zeigen Sie mithilfe des Pumping-Lemmas, dass die Sprache
L={w∈Σ∗: |w| ist eine Primzahl } über dem Alphabet Σ = {”Frohe“,”Adventszeit“} nicht regular ist.
1 Antwort
Etwas tricky. Ich nehme an, dass du bereits mit dem Pumping-Lemma vertraut bist, daher erspar ich mir die Formalitäten.
Sei n ∈ ℕ beliebig.
Wir wählen uns ein Wort x, dass ist der Sprache liegt:
x = (frohe)^p mit p > n und p Primzahl (Satz von Euklid)
x ∈ L ist klar und |x| ≥ n
Betrachten wir uns eine beliebige Zerlegung x = uvw (nach Pumping-Lemma Def.)
Dann ist:
v = (frohe)^k für 1 ≤ k ≤ n
u v^(p+1) w = (frohes)^(p+p*k) ∉ L
(Die Länge von uv^(i+1)w = p + i*k)
p + p*k = p * (1 + k)
Also keine Primzahl.
Mit dem Pumping-Lemma folgt dann, dass L nicht regulär ist.
Laut Definition ist ein Wort eine endliche Folge von Symbolen eines Alphabets.
Die Länge eines Wortes w ist nach Definition die Anzahl der Symbole in w. Da "Frohe" ein Symbol des Alphabets darstellt wird es auch nur als 1 Zeichen behandelt.
Wow hätte nicht gedacht dass mir noch jemand schreiben wird. Danke dir ;)