alternativer Beweis

Question

Hallo,

wäre es auch möglich, das Pumping-Lemma folgendermaßen zu begründen:

a)vx enthält nur a's oder b's wie in der Lösung

b)vx enthält a's und b's :

hier gehen wir wie in der Begründung der Aufgabe 69 vor, und zwar :

für jedes gepumpte a muss zusätzlich k b's entstehen (da lzlb = (lzla)^2=k. lzla) also :

vx muss entweder leer sein (Widerspruch zu lvxl>=1)

oder vx muss mindestens 1+k Zeichen enthalten (Widerspruch zu lvwxl=<k)

Answer 1

Ich gehe mal davon aus, dass du von Wort $w=a^kb^{k^2}$ und $i=2$ ausgehst.

Dann ist deine Aussage "für jedes gepumpte a muss zusätzlich k b's entstehen" falsch. Beispiel: $w=a^2b^4$ ->k=2 -> gepumptes Wort $a^3b^9$ -> es müssen 5 b's entstehen und nicht 2

Für ein gepumptes a müssen zusätzlich $2k+1$ b's entstehen, für zwei gepumpte a's müssen zusätzlich $4k+4$ b's entstehen, für 3 müssen $6k+9$, ...

D.h. für jedes gepumpte a müssen mindestens $2k+1$ b's entstehen.

Jetzt kann man die Argumentation wie in Aufgabe 69 verwenden:

vx muss entweder leer sein -> Widerspruch
oder vx muss mindestens $2k+2$ Zeichen enthalten -> Widerspruch

Viele Grüße Philipp (Tutor)