Aufgabe:
L1 := { w#al#wR#bl | w ∈ {a,b}* , l ≥0 }
Zeigen Sie, dass die Sprache nicht kontextfrei ist.
L2 := { anbmcm | n,m ≥ 1 }
Zeigen Sie, dass die Sprache nicht regulär ist
Problem/Ansatz:
Zu L1 :
Ich weiß leider nicht wie ich hier vorgehen soll.
Zu L2 :
Wir wählen Pumping Lemma Zahl P, sodass |z| ≥ P mit z ∈ L2.
Jetzt sei z = aPbPcP ∈ L2
|z| = 3P > P
u = aP-k
v = ak
w = bPcP
uvw = aP-k (ak)i bP cP = ak(P-1+i) bPcP
Damit es jetzt kein Teil der Sprache mehr ist, müsste die Anzahl an a's 0 sein. Dies würde nur zutreffen, wenn k = 0 oder i = -(P-1) ist. Aber da i ∈ℕ0 ist und ich k nicht setzen darf geht das nicht. Oder darf ich k doch auf 0 setzen?
Mein anderer Gedanke war zu gucken ob die Anzahl der b's und c's übereinstimmen. Aber ich weiß nicht wie ich das gehen soll.