Wie wendet man das Pumping-Lemma an?

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.

Wow hätte nicht gedacht dass mir noch jemand schreiben wird. Danke dir ;)

0
Eine frage hätteich aber noch, stellt "frohe" ein Wort aus 5 zeichen da oder wird es hier als ein eigenes Zeichen behandelt ?
0
@Kroplay99

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.

0

Was möchtest Du wissen?