+1 Daumen
61 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.

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.

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community