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

Aufgabe mit Lösung Sprache a^n b^n ist nicht regulär (mit Pumping-Lemma)

Gegeben ist die folgende Sprache, die gleich viele \(a\) wie \(b\) enthält:\[ L = \{ a^n \, b^n ~:~ n \geq 1 \} \]

Zeige, dass \(L\) nicht regulär (keine Typ-3-Sprache) ist.

Lösungstipps

Benutze das folgende Pumping-Lemma für reguläre Sprachen und führe einen Widerspruchsbeweis durch:

Pumping-LemmaSei \(L\) eine reguläre Sprache. Es gibt eine Mindestlänge \(n\), sodass sich alle Wörter \(x \in L\), mit \(|x| \geq n\), in \( x = u\,v\,w\) zerlegen lassen und die Zerlegung dabei drei folgende Eigenschaften erfüllt:
1) \(|v| \geq 1 \)
2) \(|uv| \leq n \)
3) Für alle \(i \geq 0\): \(u\,v^i \, w \in L \).

Lösung

Lösung anzeigen

Um zu beweisen, dass die gegebene Sprache \(L\) nicht regulär ist, führen wir einen Widerspruchsbeweis mithilfe des Pumping-Lemmas durch (siehe Lösungstipps).

Im Grunde müssen wir dazu vier Schritte ausführen:

  1. Schritt #1: Nimm an, dass die Sprache \(L\) regulär ist.
  2. Schritt #2: Wähle ein geeignetes Wort \(x \in L \), mit \(|x| \geq n\), zum "Pumpen".
  3. Schritt #3: Betrachte alle möglichen Fälle, wie \(x\) in \(u\,v\,w\) aufgeteilt werden kann.
  4. Schritt #4: Zeige durch das "Aufpumpen", dass keine der möglichen Aufteilungen, gleichzeitig alle drei Eigenschaften des Pumping-Lemmas erfüllen.

Führen wir die Schritte nun durch:

Schritt #1

Sei \(L\) regulär. Dann gibt es nach dem Pumping-Lemma eine Mindestlänge \(n\), sodass sich alle Wörter \(x\in L\) mit mindestens der Länge \(n\) zerlegen lassen in \( x = u\,v\,w\) und dabei die drei Eigenschaften des Pumping-Lemmas erfüllen.

Schritt #2

Wähle das Wort: \[ x ~=~ a^n \, b^n \]Das Wort ist in der Sprache: \( x\in L\).
Die Länge \(|x| = 2n\) des gewählten Wortes \(x\) ist größer als die Mindestlänge: \(|x| \geq n\).
Das Wort ist also geeignet.

Schritt #3

Nun wird das gewählte Wort \(x\) in \(u\,v\,w\) aufgeteilt.

Fall #1: Der mittlere Wortteil \(v\) besteht nur aus \(a\)-Symbolen:\[ u\,v\,w ~=~ a^k \, a^m \, b^n \]mit \(k+m = n\).

Fall #2: Der mittlere Wortteil \(v\) besteht nur aus \(b\)-Symbolen:\[ u\,v\,w ~=~ a^n \, b^k \, b^m \]mit \(k+m = n\).

Fall #3: Der mittlere Wortteil \(v\) besteht aus \(a\)- und \(b\)-Symbolen:\[ u\,v\,w ~=~ a^k \, a^m \, b^s \, b^r \]mit \(k+m = n\) und \(s+r = n\).

Schritt #4

In diesem letzten Schritt zeigen wir, dass bei allen im vorherigen Schritt betrachteten Aufteilungen, mindestens eine Eigenschaft des Pumping-Lemmas verletzt wird.

Fall #1: Der mittlere Wortteil \(v\) besteht nur aus \(a\)-Symbolen:
Wir wählen \(i=2\). Das aufgepumpte Wort ist dann:\[ u \, v^2 \, w ~=~ a^k \, a^{2m} \, b^n \]Offensichtlich ist \( k + 2m\) größer als \(n\), denn \( k + m = n\). Es gibt also mehr \(a\)- als \(b\)-Symbole. Damit ist die dritte Eigenschaft verletzt, denn das Wort \(a^k \, b^{2m} \, b^n\) gehört nicht zur Sprache \(L\).

Fall #2: Der mittlere Wortteil \(v\) besteht nur aus \(b\)-Symbolen:
Wir wählen \(i=2\). Das aufgepumpte Wort ist dann:\[ u \, v^2 \, w ~=~ a^n \, b^{2m} \, b^k \]Offensichtlich ist \( 2m + k\) größer als \(n\), denn \( m + k = n\). Es gibt also mehr \(b\)- als \(a\)-Symbole. Damit ist die dritte Eigenschaft verletzt, denn das Wort \(a^n \, b^{2m} \, b^k\) gehört nicht zur Sprache \(L\).

Fall #3: Der mittlere Wortteil \(v\) besteht aus \(a\)- und \(b\)-Symbolen:
Wir wählen \(i=2\). Das aufgepumpte Wort ist dann:\[ u \, v^2 \, w ~=~ a^k \, (a^m \, b^s \, a^m \, b^s) \, b^r \]Das aufgepumpte Wort ist nicht in der Sprache, weil nach dem \(b\)-Symbol wieder ein \(a\)-Symbol folgt. Damit ist die dritte Eigenschaft verletzt.

Wir haben damit gezeigt, dass keine der möglichen Aufteilungen \(u\,v\,w\) gleichzeitig alle drei Eigenschaften des Pumping-Lemmas erfüllen. Das ist ein Widerspruch zu der Annahme, dass \(L\) regulär ist. Foglich ist \(L\) nicht regulär.

Die \(a\)'s und \(b\)'s könnten genauso 1en und 0en sein oder öffnende "(" und schließende ")" Klammern. Der Beweis für derartige Sprachen geht genauso wie für \(a\)'s und \(b\)'s.
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?