Zeigen Sie anhand des Pumping-Lemmas, dass die folgende Sprache nicht kontextfrei ist:

Question

Aufgabe:

Zeigen Sie anhand des Pumping-Lemmas, dass die folgende Sprache nicht kontextfrei ist:

(i) \( L_{1}=\left\{a^{i} b^{j} \mid i \geq 0, j=i^{2}\right\} \) über \( \Sigma=\{a, b\} \)

(ii) \( L_{2}=\left\{a^{i} b^{i} c a^{i} b^{i} \mid i \geq 0\right\} \) über \( \Sigma=\{a, b\} \)

Ansatz/Problem:

Sobald es zur Aufteilung in in die drei Variablen (bei uns "uvw") kommt versagt jeder meiner Ansätze.

Answer 1

Hier geht es nicht um reguläre Sprachen, sondern um kontextfreie Sprachen. Du brauchst also nicht eine Aufteilung z=uvw finden. Stattdessen genügt es, ein Wort z zu finden, so dass jede Aufteilung z=uvwxy die den im Pumpinglemma für kontextfreie Sprachen genannten Eigenschaften wiederspricht.