Vorgehensweise bei PPL für kontextfreie Sprachen

Question

Allgemein bin ich von dem Vorgehen des PPL bei kontextfreien Sprachen verwirrt.

Beim PPL bei regulären Sprachen ist mir das Vorgehen klar und relativ logisch, also dass man sich x y und z definiert und dann ein i sucht bei dem der Ausdruck der Definition der Sprache widerspricht etc..(also es nur grob und schnell dahin gesagt, ich weiß das müsste besser beschrieben werden, aber darum gehts mir ja gerade nicht ;))

Aber bei den kontextfreien scheint es für mich bei jeder Aufgabe ein andere Art von Lösungsweg zu geben, die ziemlich lang und komplex ist. Wieso kann man hier nicht vorgehen wie bei regulären Sprachen?

Ich weiß, dass reguläre Sprache nur eine und kontextfreie Sprachen 2 Pumpstellen haben.

Aber ich bin einfach komplett verwirrt von den kontextfreien PPL und hätte dazu gerne eine anschauliche Erklärung, wie man an solche Aufgaben am besten dran geht und was eigentlich die Logik dahinter ist.

 

Answer 1

Die Vorgehensweise beim PPL für reguläre Sprachen bzw. beim PPL für kontextfreie Sprachen ist eigentlich vom Prinzip her sehr ähnlich. Ich erkläre das hier kurz am Beispiel des PPL für kontextfreie Sprachen.

Wenn eine Sprache kontextfrei ist, dann existiert eine Zahl $k∈N_0$ bei der für alle Wörter z in L mit $|z| \geq k$ eine Zerlegung $z = uvwzy$ existiert, für die gilt

(1) $|vwx| \leq k$

(2)$vx ≠λ$

(3) für alle $i∈N_0:uv^iwx^iy∈L$

Wenn Sie jetzt zeigen wollen, dass eine Sprache das PPL nicht erfüllt, dann müssen Sie diese Annahmen also widerlegen (wichtig werden jetzt die oben unterstrichenen Quantoren):

Also müssen sie für ein Wort z (beim PPL gilt es für alle) und alle hier möglichen Zerlegungen (vgl. oben es existiert eine Zerlegung), die die Bedingungen (1) und (2) erfüllen, zeigen, dass es mindestens ein i gibt (beim PPL für alle i) für welches $<span>i \in N_0: uv^iwx^iy \notin L$. Wenn Sie dies gezeigt haben, dann ist das ein Widerspruch zur Aussage des PPL und die Sprache ist nicht kontextfrei.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König