+1 Daumen
678 Aufrufe

Aufgabe:

L1 := { w#al#wR#bl | w ∈ {a,b}* , l ≥0 }

Zeigen Sie, dass die Sprache nicht kontextfrei ist.

L2 := { anbmc| 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.

Avatar von

Bitte bei den "ähnlichen Fragen" unten schauen. Das läuft häufig unter "theoretischer Informatik", daher sind viele "ähnliche Fragen" auch in der stacklounge zu finden. Link jeweils bei den geschlossenen (verschobenen) Fragen nutzen. Bitte Duplikate vermeiden helfen und Links jeweils angeben, falls du Duplikate findest.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community