1. Welt
  2. Quests
  3. #1459
Alexander Fufaev

Nicht-kontextfreie Sprache - Pumping-Lemma

aus dem Bereich: Quests
Mehr dazu

    Deine Aufgabe ist...

    Zeige, dass die folgende Sprache \(L\) nicht kontextfrei ist:

    1. \( L = \{ a^j \, b^k \, c^{j+k} \, d^j ~|~ j,\,k \geq 0 \} \)
    2. \( L = \{ w \, w ~|~ w \in \{0,1\}^{*} \} \)
    Allgemeine Lösungstipps

    Benutze das Pumping-Lemma für kontextfreie Sprachen.

    Lösung zu (a) anzeigen

    Die Sprache \(L\) enthält beispielsweise folgende Wörter: \[ L = \{ \varepsilon, ~a\,b\,c^2 \, d, ~ a^2 \, b^3 \, c^5 \, d^2, ~ a\,c\,d, ~...\} \]

    Sei \(L\) kontextfrei. Dann muss es nach dem Pumping-Lemma für kontextfreie Sprachen ein \(n \in \mathbb{N}\) geben, sodass sich alle Wörter \(z \in L\), mit \(|z| \geq n\), zerlegen lassen in \( z = u\,v\,w\,x\,y \), wobei folgende drei Eigenschaften gelten müssen:

    • 1) \( |v\,x| \geq 1 \)
    • 2) \( |v\,w\,x| \leq n \)
    • 3) \(\forall i \geq 0\): \( u \, v^i \, w \, x^i \, y \in L\)

    Wähle das Wort \(z = a^n \, c^n \, d^n\) mit \(k=0\). Dieses Wort ist in der Sprache und erfüllt \( |z|=3n \geq n \). Jetzt müssen alle möglichen Fälle durchgegangen werden, an welcher Stelle des Wortes \(z\) das Teilwort \(v\,w\,x\) stehen könnte.

    Fall #1
    Das Teilwort \(v\,w\,x\) enthält mindestens ein \(a\). Da das Teilwort \(v\,w\,x\) höchstens \(n\) lang sein kann (zweite Eigenschaft), kann das Teilwort kein \(d\) enthalten. Für \(i=2\) ist dann das "aufgepumpte" Wort \( u \, v^2 \, w \, x^2 \, y\) nicht in der Sprache, weil es mehr \(a\)'s als \(d\)'s enthält. Das aufgepumpte Wort ist nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Fall #2
    Das Teilwort \(v\,w\,x\) enthält mindestens ein \(d\). Da das Teilwort \(v\,w\,x\) höchstens \(n\) lang sein kann (zweite Eigenschaft), kann das Teilwort kein \(a\) enthalten. Für \(i=2\) ist dann das "aufgepumpte" Wort \( u \, v^2 \, w \, x^2 \, y\) nicht in der Sprache, weil es mehr \(d\)'s als \(a\)'s enthält. Das aufgepumpte Wort ist nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Fall #3
    Das Teilwort \(v\,w\,x\) enthält nur \(c\)'s. Da das Teilwort \(v\,w\,x\) höchstens \(n\) lang sein kann (zweite Eigenschaft), kann das Teilwort keine \(a\)'s und \(d\)'s enthalten. Für \(i=0\) ist dann das "abgepumpte" Wort \( u \, v^0 \, w \, x^0 \, y\) nicht in der Sprache, weil es mehr \(c\)'s als \(a\)'s und \(d\)'s enthält. Das aufgepumpte Wort ist nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Da mit den drei Fällen alle möglichen Fälle der Zerlegung betrachtet wurden, ist in keinem die dritte Eigenschaft erfüllt. Widerspruch zu der Annahme. \(L\) ist nicht kontextfrei.

    Lösung zu (b) anzeigen

    Die Sprache \(L\) besteht aus einem Wort, dessen erster Wortteil gleich dem zweiten Wortteil ist. Zum Beispiel: \(0101\), \(000111000111\), \(11\) oder \(00\).

    Sei \(L\) kontextfrei. Dann muss es nach dem Pumping-Lemma für kontextfreie Sprachen ein \(n \in \mathbb{N}\) geben, sodass sich alle Wörter \(z \in L\), mit \(|z| \geq n\), zerlegen lassen in \( z = u\,v\,w\,x\,y \), wobei folgende drei Eigenschaften gelten müssen:

    • 1) \( |v\,x| \geq 1 \)
    • 2) \( |v\,w\,x| \leq n \)
    • 3) \(\forall i \geq 0\): \( u \, v^i \, w \, x^i \, y \in L\)

    Wähle das Wort \(z = 0^n \, 1^n \, 0^n \, 1^n\). Dieses Wort ist in der Sprache und erfüllt \( |z|=4n \geq n \). Jetzt müssen alle möglichen Fälle durchgegangen werden, an welcher Stelle des Wortes \(z\) das Teilwort \(v\,w\,x\) stehen könnte.

    Fall #1
    Das Teilwort \(v\,w\,x\) befindet sich im ersten 0er Block von \(z\). Da das Teilwort \(v\,w\,x\) höchstens \(n\) lang sein kann (zweite Eigenschaft), kann das Teilwort keine 0en des zweiten 0er-Blocks enthalten. Denn dazwischen liegen \(n\) 1en. Für \(i=2\) ist dann das "aufgepumpte" Wort \( u \, v^2 \, w \, x^2 \, y\) nicht in der Sprache, weil es mehr 0en im ersten Teilwort \(0^{n+k} \, 1^n\) (\(k\geq 0\)) enthält als 0en im zweiten Teilwort \(0^n \, 1^n\). Das aufgepumpte Wort ist nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Fall #2
    Das Teilwort \(v\,w\,x\) befindet sich komplett im zweiten 1er Block von \(z\). Da das Teilwort \(v\,w\,x\) höchstens \(n\) lang sein kann (zweite Eigenschaft), kann das Teilwort keine 1en des ersten 1er-Blocks enthalten. Denn dazwischen liegen \(n\) 0en. Für \(i=2\) ist dann das "aufgepumpte" Wort \( u \, v^2 \, w \, x^2 \, y\) nicht in der Sprache, weil es mehr 1en im zweiten Teilwort \(0^n \, 1^{n+k} \) (\(k\geq 0\)) enthält als 1en im ersten Teilwort \(0^n \, 1^n\). Das aufgepumpte Wort ist nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Fall #3
    Das Teilwort \(v\,w\,x\) enthält mindestens eine 1 des ersten 1er Blocks von \(z\). Es hat also keine 1en des zweiten 1er Blocks. Für \(i=0\) ist das "abgepumpte" Wort \( u \, v^0 \, w \, x^0 \, y \) = \( 0^{n-m}\,1^{n-l}\,0^{n-k}\,1^r \), für passende \(l, m, k, r \geq 1 \). Durch das Abpumpen können aber (nach der zweiten Eigenschaft) maximal \(n\) Symbole gelöscht werden. Der zweite 1er Block bleibt unberührt. Es liegen mindestens \(n\) 1en im zweiten Wortteil, jedoch maximal \(n-m = n-1\) im ersten Wortteil. Das abgepumpte Wort ist nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Fall #4
    Das Teilwort \(v\,w\,x\) enthält mindestens eine 0 des ersten 0er Blocks von \(z\). Es hat also (wegen der zweiten Eigenschaft) keine 0en des zweiten 0er Blocks. Für \(i=0\) ist das "abgepumpte" Wort \( u \, v^0 \, w \, x^0 \, y \) nicht in der Sprache. Widerspruch zur dritten Eigenschaft.

    Weltkarte
    Verwalten
    Profil
    Die Stimme fragt...
    Wie erlange ich den Zugang?

    Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

    • Inhalte hinzufügen & verwalten
    • Illustrationen ohne Copyrightzeichen herunterladen
    • Einige Inhalte kommentieren
    • Mittels Kommunikator RT2000 chatten
    • Telegram-Gruppe beitreten
    Bist Du dabei?
    Ja, bin dabei!
    Portale in die anderen Welten

    Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

    Portalraum betreten
    Kommunikator
    ONLINE 2
    Gäste online: 1
    Denker online: 1
    Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
    Ich will in die Matrix!Mayday! Kontakt aufnehmen.