Erklärung PPL (2)

Question

Ich versuche gerade die Lösung nachzuvollziehen, komme aber nicht weiter. Wenn x=lambda, |y| = 1, |z| = |w| -1 gilt, dann kann y doch nur a oder b sein und nicht wie in der Lösung beschrieben a, b oder c. 

Ich habe das PPL selbst versucht zu beweisen, ist das so korrekt?

 

Answer 1

Hallo!

Zu deiner ersten Frage: Der zweite Teil der Vereinigung in der Lösung ist die Sprache b^m c^n. b,n>=0. Wenn das Wort also aus dieser Sprache L´´ kommt und m 0 ist ist y ein c.

Zu deinem Beweis: Du zeigst das PL nur für die Sprache L´. Außerdem wird der Weg den du benutzt meistens benutzt um zu zeiden, dass das Pumping Lemma nicht gilt. Als Tipp kann ich dir mitgeben, dass du dir eher eine logische Erklärung suchst, um zu zeigen, dass das PL gilt und diese dann auszuformulieren.

Felix(Tutor)

 

PS: Die Lösung nochmal kurz erklärt: wir wollen ja zeigen, dass es für jedes wort EINE Zerlegung gibt, in der man y pumpen kann. In beiden Sprachen L´ und L´´ kann man den ersten Buchstaben immer pumpen. Wie in der Lösung beschrieben, zerlegt man das Wort also so, dass y nur der erste Buchstabe ist und kann dann y pumpen. Also gilt das PL.

Answer 2

Ich bin nicht sicher, was Sie hier versuchen, denn Sie beziehen sich ja nur auf einen Teil der Sprache $L_1$. Wichtig ist zu verstehen, dass wir hier ausnahmsweise andersherum vorgehen als sonst - wir wollen diesmal wirklich eine Zerlegung finden, sodass die Eigenschaften (1), (2) und (3) gelten. Und nicht - wie normalerweise - zeigen, dass es keine Zerlegung gibt, für die diese Eigenschaften gelten.

In Ihrer Argumentation schreiben Sie, $xy$ könne nur zwei der drei Buchstaben enthalten - dabei sind Sie aber auf der klassischen Schiene mit dem Widerspruchsbeweis. Stattdessen können wir es uns diesmal leicht machen und tatsächlich eine Zerlegung auswählen. Es reicht uns, eine zu finden, wir müssen nicht über alle argumentieren.

Und diese eine legen wir einfach fest durch

• $x=\lambda$,
• $|y| = 1$,
• $z$ = der ganze Rest des Wortes $w$.

$y$ ist also gerade das erste Zeichen des Wortes $w$. Offenbar sind die drei Eigenschaften so erfüllt. Und nun kann es immer noch zwei Fälle geben: Entweder ist $y=a$ oder $y \neq a$. Ist $y=a$, gilt $$w=a^\star b^nc^n \in L_1$$ Pumpen wir nun zu $xy^iz$, verändern wir nur die Anzahl an $a$'s, also bleiben wir in der Sprache (das muss in dieser Beweisrichtung für alle $i$ gelten, hier dürfen wir uns also kein $i$ aussuchen!).

Ist dagegen $y \neq a$, ist das Wort $$w=b^\star c^\star \in L_1$$ Egal, ob es dann überhaupt $b$'s gibt oder nicht, ob also $y=b$ oder $y=c$, die relative Anzahl an $b$'s und $c$'s ist im Fall, dass es keine $a$'s im Wort gibt nicht spezifiziert, also bleibt jedes beliebige $xy^iz$ in der Sprache.

Damit sind wir fertig: Für jedes Wort $w$ ab einer gewissen Größe gibt es eine Zerlegung mit (1), (2) und (3) erfüllt.

Comments

Ich glaube du hast dich vertippt. Du wolltest wahrscheinlich schreiben:
... Ist dagegen $y \neq a$, ist das Wort ....

---

Richtig, ich korrigere es. Danke.