Formaler Frage bei Fallunterscheidung des PPL für kontextfreie Sprachen

Question

Ich habe eine Frage zur Aufgabe 3.

Hier definieren wir in den 5 Fällen ja vwx= ... Müsste es hier nicht formal korrekt heißen, dass vx =..., also zB vx= a^m statt  vwx= a^m in Fall 1?
In der Lösung wird behauptet, dass etwa bei vwx = a^m gelte: für i=0 lautet das gepumpte Wort:  a^(k-m)b^(2k)c^(3k).
Vernachlässigen wir dabei nicht, dass w (welches nicht gepumpt und damit nicht rausgelöscht wird) ebenso Teile der a's enthalten kann, sodass die Anzahl der a's nach dem Pumpen nicht zwingend a^(k-m) wäre? Der Widerspruchsbeweis würde ja denke ich trotzdem funktionieren, da durch |vx|>=1 immer mindestens ein a (für i=0) gelöscht würde und somit das Verhältnis der a's zu den b's und c's gestört wäre..
Oder darf man trotz beliebiger Zerlegungen (bzw trotz aller möglichen Zerlegungen, die man formal überprüfen muss) davon ausgehen, dass w leer ist?

Vielen Dank für Eure Hilfe!

Answer 1

Ja, du hast Recht. $vx=a^m$ mit $m \leq k - |w|$ wäre besser, denn dann würde auch das mit i=0 gepumpte Wort $a^{k-m}b^{2k}c^{3k}$ lauten.

Und nein, man darf nicht annehmen, dass w immer leer ist.

Viele Grüße

Philipp (Tutor)

Comments

Vielen Dank :)