Beziehung zu |z| >= n

Question

wenn wir in z jetzt bei kontextfreien Sprachen z.b. kein Mal durch die Schleife laufen, was ja genau dem i = 0 entsprechen müsste, dann habe ich doch nicht mehr mit Sicherheit gegeben, dass |z| >= n ist. Damit wäre dann doch auch die Grundlage der Eigenschaften für die Argumentation des PPLs hinfällig, oder nicht?

Wie wäre das dann analog bei dem PPL der regulären Sprachen zu verstehen?

 

Die Frage bezieht sich auf diesen Beitrag: https://info2.aifb.kit.edu/qa/index.php?qa=5207&qa_1=pumpen-mit-i-0

Answer 1

Hallo,

das muss auch nicht gelten für i=0, wie du ja schon geschrieben hast, die Schleifen müssen nicht durchlaufen werden.

Die Sprache muss Pumpstellen haben (sonst könnte man nur endlich viele Wörter erzeugen).

Die Idee dahinter ist eine andere: Du nimmst ein Wort z, das mindestens n Zeichen lang ist. Dies ist die Vorraussetzung.
Dein gewähltes Wort z beinhaltet also auch eine Pumpstelle, sonst wäre es nicht mindestens n Zeichen lang. Die Schleife muss aber nicht zwangsläufig durchlaufen werden (i=0), dann ist das modifizierte Wort möglicherweiße kürzer als n Zeichen, aber es muss immer noch zur Sprache gehören, da man die Pumpstelle (von z) beliebig oft pumpen kann (i=0,1,2,...).
Also ist die Grundlage nicht hinfällig, da immer noch gilt |z| >= n.

Das selbe Prinzip gilt auch bei dem PPL für reguläre Sprachen.

Ich hoffe es ist nun klarer, wenn du noch Fragen hast kannst du gerne noch einmal schreiben.

Viele Grüße
Anne (Tutor)