c): i für jede denkbare Zerlegung z ?

Question

Ich habe eine Frage zu Aufgabenteil c): Muss man für jede (!) denkbare Zerlegung von z ein i finden, für das das Wort uv^(i)wx^(i)y nicht in L liegt?

Answer 1

Hallo,

das PPL besagt, dass jedes Wort (größer gleich der PPL-Konstante k) aus einer kontextfreien Sprache eine Zerlegung besitzt, die die 3 Bedingungen erfüllt

Im Umkehrschluss bedeutet das, dass das PPL nur dann nicht erfüllt ist (also das Wort nicht aus einer kontextfreien Sprache  ist), wenn ein solches Wort mit keiner Zerlegung die Bedingungen erfüllt. Deshalb müssen alle Zerlegungen überpürft werden, was am einfachsten durch die Bildung von Fällen geschieht.

Viele Grüße

Philippe (Tutor)