0 Daumen
129 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen

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.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community