Widerspruchsbeweis mit dem Pumping-Lemma

Question

Hallo,
Wie lautet denn die Erklärung dafür dass die letzte aussage falsch ist?
Vielen dank

Answer 1

Das Pumping-Lemma für kontextfreie Sprachen ist nicht so einfach in das PL für reguläre Sprachen transformierbar.

Wenn du dir die Bedingungen, die an die Zerlegung eines Wortes für das PL für kontextfreie Sprachen gestellt werden, anschaust, sollte deutlich werden, dass man nicht einfach eine Pumpingvariable gleich 0 setzen kann, um daraus die Bedingungen für das PL für reguläre Sprachen zu erhalten.

Zudem gilt, dass im PL für kontextfreie Sprachen die Wörter an den zwei Pumpstellen mit dem gleichen i gepumpt werden müssen (uv^iwx^iy). Deshalb kann man nicht einfach ein i=0 setzen und dem anderen i einen anderen Wert zuordnen.

Grüße,

Melanie (Tutorin)