Vollständiger Beweis nötig oder reicht 1 Teilschritt?

Question

Hallo,

muss man wie in der Lösung alle verschiedenen Mgk testen so wie in der Lösung oder würde es auch reichen, einen der drei Beweispunkte vx = a^sb^t..... zu führen. 

a,b € {0,1,2,3}

Gruß

 

Answer 1

Hallo,

nach dem PPL muss ja nur eine solche Zerlegung existieren, damit L kontextfrei ist. Im Umkehrschluss heißt das, dass alle Zerlegungen deines Wortes für den Beweis, dass L nicht kontextfrei ist, zu einem Widerspruch führen müssen.

Würdest du also nur einen der Beweispunkte durchführen, wäre der Beweis unvollständig, da eine der anderen Möglichkeiten evtl. nicht zu einem Widerspruch führt. Deshalb müssen alle gezeigt werden.

Viele Grüße

Philippe (Tutor)

 

Comments

Wäre dann aber die Aufgeführte Lösung auch nicht ganz komplett?? Denn es fehlen die Fälle, wo vxy nur aus 0, 1, 2 oder 3 besteht. Da müsste man doch auch einen formalen Widerspruch liefern...

Wäre es nicth bei solchen Aufgaben sinnvoll, wie bei den anderen PL zu kontextfreien Sprachen, mit Text zu argumentieren, sodass man nicth der Gefahr entgegenläuft, einen möglichen Fall zu bersehen??

lg

---

Nein, das ist darin enthalten, dass s und t aus N inklusive 0 sind. Es gilt lediglich, dass s+t > 0 sein muss.

Ich denke, das ist geschmackssache. Wenn man allerdings rein textuell argumentiert, besteht die Gefahr, dass man die Begründung nur unzureichend ausführt. Dafür ist die Erklärung für die meisten aber wahrscheinlich intuitiver.

Viele Grüße

Philippe (Tutor)

Answer 2

Wie schon gesagt wurde, müssen alle Möglichkeiten durchgegangen werden.

 

Man kann das Pumping-Lemma übrigens auch als eine Art Spiel auffassen (man selbst spielt sozusagen "gegen das Pumping-Lemma"), wie es in einem Beitrag bei Stackexchange erklärt wird. Ich finde, das ist eine sehr schöne und intuitive Art, sich das Vorgehen klarzumachen, und vielleicht hilft es Ihnen auch beim Verständnis:

---

Here is an example for the pumping lemma: suppose the language $L=\{ a^k \mid k ∈ P\}$ is context free ($P$ is the set of prime numbers). The pumping lemma has a lot of $∃/∀$ quantifiers, so I will make this a bit like a game:

 

  1. The pumping lemma gives you a $p$

  2. You give a word $s$ of the language of length at least $p$

  3. The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)

  4. You give an integer $n≥0$

  5. If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

 

For this particular language for $s$ any $a^k$ (with $k≥p$ and $k$ is 

a prime number) will do the trick. Then the pumping lemma gives you 

$uvxyz$ with $|vy|≥1$. To disprove the context-freeness, you need to

find $n$ such that $|uv^nxy^nz|$ is not a prime number.

 

$$|uv^nxy^nz|=|s|+(n-1)|vy|=k+(n-1)|vy|$$

 

And then $n=k+1$ will do: $k+k|vy|=k(1+|vy|)$ is not prime so $uv^nxy^nz\not\in L$. The pumping lemma can't be applied so $L$ is not context free.

---

Die Variable $p$ nennen wir normalerweise $n$, und die Pumpvariable, die hier $n$ genannt wurde, ist bei uns gewöhnlich $i$. Das Vorgehen funktioniert analog auch beim Pumping-Lemma für reguläre Sprachen.

 

Vergleichen Sie hierzu auch den Beweis, dass die obige Sprache $L$ nicht regulär ist aus Aufgabe HU-1-4.