Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #348

Aufgabe mit Lösung Nicht-kontextfreie Sprache - Pumping-Lemma

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\}^{*} \} \)
Lösungstipps

Benutze das Pumping-Lemma für kontextfreie Sprachen.

Lösung

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.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?