Pumping Lemma Bedingung |uv| <= p: Wieso nicht auch bs?

Question

Frage: Pumping Lemma Bedingung |uv| <= p

Folgendes habe ich von einer Website kopiert. Nicht unbedingt für die Frage relevant aber als Leitpfad und Kontext. Es geht mehr ums generelle Verstehen der Bedingung 2. Ich verstehe nicht warum |uv| kleiner gleich p gelten muss. Und warum man dadurch weiß, dass in dem Beispiel a hoch n b hoch n, im Teilwort uv nur a's vorkommen müssen. Wieso nicht auch b's? Aber nicht unbedingt nur auf dieses Beispiel bezogen. Mir wurde es versucht zu erklären im Sinne von, dass es da eine Beschränkung geben muss, aber mir ist nicht klar warum.

Satz:  Die Sprache L = { a^n*b^n  |  n Element natürliche Zahlen } ist nicht regulär.

Beweis:  Angenommen, L wäre regulär. Dann gilt das Pumping-Lemma. Sei nun p die Pumping-Länge und sei x = a^p*b^p. Dann gilt |x|größer gleichp und x lässt sich somit darstellen als x  = uvw mit

|v| > 0

|uv| kleiner gleich p

Da |uv|kleiner gleich p, besteht uv nur aus a's, und damit besteht auch v nur aus a's. Sei r die Länge von v; es gilt r > 0. Dann ist nach dem Pumping-Lemma auch uv^2w  = a^p+r * b^p  Element  L, im Widerspruch zur Definition von L. Also ist die Annahme falsch, L ist also nicht regulär.

Die Anwendung des Pumping-Lemmas verläuft immer nach diesem Schema. Wir nehmen an, dass L regulär ist. Dann gilt das Pumping-Lemma, und es gibt somit eine Pumping-Länge p.

Jetzt müssen wir nur ein einziges Wort x Element L finden, das lang genug ist, d.h. mit |x|größer gleich p, und ein Anfangswort uv von x, das kurz genug ist, d.h. mit |uv|kleiner gleichp, und das so beschaffen ist, dass wir in uv einen beliebigen Teil v "aufpumpen" können, um Wörter zu erhalten, die nicht in L liegen. Damit erhalten wir einen Widerspruch zur Annahme, dass L regulär ist.

In obigem Beweis haben wir dafür gesorgt, dass uv nur aus a's besteht. Somit besteht auch das Teilwort v nur aus a's, ganz gleich, welchen Teil von uv es einnimmt. Wird nun v "aufgepumpt", so entstehen Wörter mit mehr a's als b's, also Wörter, die nicht in L liegen. Damit kann L nicht regulär sein.

Answer 1

Pumping Lemma: Ist L eine reguläre Sprache, dann gibt es eine Zahl p, so dass sich jedes Wort z ∈ L mit |z| ≥ p in drei Teile z = uvw zerlegen lässt, so dass gilt

1. |v| > 0,
2. |uv| ≤ p,
3. uvⁿw ∈ L für jedes n ∈ ℕ.

Es gibt Sprachen, die den dann-Teil erfüllen obwohl sie nicht regulär sind.

Lässt man Bedingung 2 weg, dann gibt es vielleicht noch mehr Sprachen, die den dann-Teil erfüllen obwohl sie nicht regulär sind.

Ein ähnlicher Satz: Ist n ein Vielfaches von 12, dann gilt:

1. n ist ein Vielfaches von 2,
2. n ist ein Vielfaches von 3.

Diesen Satz kann man verwenden, um zu beweisen, dass 16 nicht durch 12 teilbar ist. Und zwar indem man zeigt, dass 16 nicht durch 3 teilbar.

Lässt man jetzt "n ist ein Vielfaches von 3" weg, dann kann man mit diesem Satz nicht mehr zeigen, dass 16 nicht durch 12 teilbar ist. Man müsste sich dann eine andere Strategie überlegen.

Answer 2

Zu deiner Frage, warum im Teilwort nur a's vorkommen müssen:

Es gilt ja, dass die Länge von \(uv\leq p\) sein muss. Wenn man jetzt aber das Wort \(w=a^p.b^p\) betrachtet, merkt man sofort, dass schon die a's genau \(p\) Mal vorkommen. Also wenn mindestens ein \(b\) im Teilwort \(uv\) wäre, dann wäre die Eigenschaft, dass die Länge von \(uv\) kleiner gleich \(p\) ist, verletzt. Denn \(a^p.b^1\) hat eine Länge von \(p+1\) und das ist ja gerade größer als \(p\) und nicht kleiner gleich \(p\). Daher können im vorderen Teil \(uv\) nur a's enthalten sein.

Der Beweis nochmal etwas anders formuliert:

Beweis: Angenommen, \(L\) ist regulär. Dann gibt es eine Pumpinglänge \(p>0\). Wir wählen nun das Wort \(w'=a^p.b^p\), welches in \(L\) ist. Außerdem gilt \(\lvert w\rvert \geq p\). Sei \(u,v,w\in\Sigma^*\) beliebig und gelte \(\lvert uv\rvert \leq p\) und \(\lvert v\rvert >0\). Dann müssen in \(u\) und \(v\) nur a's enthalten sein, egal welche Einteilung wir vornehmen.
Sei \(u:=a^k, v:=a^l\) mit \(k,l\in \mathbb{N}\), \(k+l\leq n, l>0\) und \(w:=a^{p-l-k}.b^p\). Betrachten wir jetzt \(i=2\), haben wir:

\(\begin{aligned}uv^2w&=a^k.v^{2l}.a^{p-k-l}.b^{p}\\&=a^{p+l}.b^p, \end{aligned}\)
wobei \(\lvert a^{p+l}\rvert>\lvert b^p\rvert\), weil \(l>0\) ist. Daraus folgt sofort, dass \(uv^2w\notin L\). Widerspruch, die PE ist nicht erfüllt und \(L\) war nicht regulär. \(\square\)