Blatt 4 #1

[Johann]

Es gilt zu zeigen, dass die gegebene Sprache nicht kontextfrei ist. Ich hab das jetzt über das Pumping-Lemma für kontextfreie Sprachen probiert. Wenn ich das allerdings verstanden habe, müsste die Sprache kontextfrei sein, was ich nicht glaube. Mein Ansatz:

Man nehme das Wort a^p b^p c^p wobei p die Pumping-Lemma-Zahl ist. Dann lässt sich das Wort aber problemlos in uvxyz zerlegen, so dass Pumpen geht:

Code: Alles auswählen

...aaaaa bbbbbbbbb cccc.....
                uv xyz
                
wobei #a = p, #b = p, #c = p

Nun besagt, dass ich v und y pumpen kann und das neue Wort noch immer in L liegt. Was ja auch stimmt. Damit habe ich doch aber eine Zerlegung gefunden, womit das Pumping-Lemma gilt?

Ich habe schon die letzte Aufgabe ("Zeigen Sie, dass L nicht regulär ist") mit dem Satz von Myhill-Nerode gelöst, nicht mit dem Pumping-Lemma. Aber das muss hier doch auch gehen?


Edit: Achja, das Pumping-Lemma verlangt, dass alle Wörter w mit |w| >= p so zerlegbar sind. Aber da seh ich auch kein Problem.

Edit2: Ah, der fiese Fall hoch Null. Liegen v und y wie ich gesagt habe, würde v^0 und y^0 dafür sorgen, dass #a = #b+1 = #c+1 wäre und damit nicht mehr Element der Sprache

[DavidHume]

Ich hab das jetzt über das Pumping-Lemma für kontextfreie Sprachen probiert. Wenn ich das allerdings verstanden habe, müsste die Sprache kontextfrei sein,

... womit das Pumping-Lemma gilt?

Auch wenn das PL für die Sprache gelten würde, hättest du eigentlich nichts gezeigt, insbesondere auch nicht, dass die Sprache kontextfrei ist... Das PL lässt sich nur in der anderen Richtung anwenden, um lediglich Nichtkontextfreiheit zu zeigen. In der Argumentation sind halt beliebige bzw. alle möglichen denkbaren Zerlegungen zu betrachten. Ein Test für nur eine oder manche Zerlegungen reicht nicht aus.

[Johann]

Ja du hast schon recht, aber ich bin schwer davon ausgegangen, dass wir hier nicht gerade eine der Spezialsprachen bekommen haben, die zwar das Pumping-Lemma erfüllen, aber dennoch nicht regulär/kontextfrei sind. Daher wäre es schon seltsam, wenn ich jetzt rausgefunden hätte, es würde funktionieren. Aber das tut es offensichtlich ja nicht, nur in zwei Fällen (oder drei, keine Ahung mehr) ließ sich nur durch v^0 y^0 zeigen, dass die Zerlegung ungültig ist.