Zusammenhang der kontextfreiensprache in Grammatik in Bezug zum PPL

Question

Hallo an Alle,

Ich frage mich, wieso bei den kontextfreien Sprachen immer gegeben sein soll, dass es zwei Pumpstellen bei hinreichend großen Wörtern gibt. Grundsätzlich habe ich das Konzept, dass bei längeren Wörtern als Anzahl an Zuständen vorhanden ist, es Schleifen in der Grammatik geben muss, verstanden. Nun wird aber (allen voran bei dem PPL der kontextfreien Sprachen) immer wieder erklärt, dass es (1) zwei Pumpstellen gibt, die (2) immer gleich groß sein sollen. Hier sind auch noch SC der Überlegung im Text und die dazugehörige Skizze, die das Ganze erläutert:

Nun verstehe ich nicht ganz, wieso es immer zwei Pumpstellen geben muss, bzw wieso die dann auch noch gleich groß sein sollen?
Im Kopf habe ich dabei immer eine kontextfreie Sprache, die ja auch in CNF dargestellt werden kann.
Nun habe ich mir eine Grammatik überlegt, die Wörter produziert, deren Länge die Anzahl der Zustände übertrifft:

Dabei habe ich in B eine Produktion von sich selbst, was mir die Schleifen eines PPL ermöglicht. Nun kann ich mein Wort ja wie unten beschrieben ableiten, ohne , dass neben dem grün markierten B links und rechts die gleiche Menge gepumpt wird. Da jede kontextfreie Sprache in CNF dargestellt werden kann, weiß ich also nicht, woher diese immer zwei gleich großen Pumpstellen genau herkommen sollen.

Ich würde mich sehr über jede Antwort freuen, 

Grüße!

Answer 1

Hallo uzmzu,

mit dem PPL kannst du ja nur prüfen, ob eine Sprache nicht zu L1 (bzw. L3) gehört. 
Es kann natürlich sein, dass du nur eine Pumpstelle bei deiner Sprache hast, es ist ja nur Vorrausgesetzt, das bei z = uvwxy, |z| >= n und die Pumpstellen v,x mit |vx| >= 1 sein (und der dritten Bedingung). Also kann v oder x auch lamda sein.

Und natürlich können die Pumpstellen auch unterschiedlich oft gepumpt werdem. Aber man kann sie auch gleich oft pumpen und das gepumpte Wort muss immer noch in der Sprache sein. Also nur ein spezieller Fall. 

Dein Beispiel gehört zu L1, deshalb kann man mit dem PPL nicht zeigen, dass es nicht zur Sprache gehört

Es ist einfach nur das Vorgehen des PPL, dass es zwei Pumpstellen gibt, die gleich oft gepumpt werden. Deine angebrachten Punkte von dir sind für die Realisierung der individuellen Wörter des Sprache richtig.

Ich hoffe ich konnte dir weiterhelfen. Wenn es noch Unklarheiten gibt, schreibe einfach noch mal.

Viele Grüße

Anne (Tutor)