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. Benutze das folgende Pumping-Lemma für reguläre Sprachen und führe einen Widerspruchsbeweis durch:Lösungstipps
1) \(|v| \geq 1 \)
2) \(|uv| \leq n \)
3) Für alle \(i \geq 0\): \(u\,v^i \, w \in L \).
Lösungen
Lösung
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:
- Schritt #1: Nimm an, dass die Sprache \(L\) regulär ist.
- Schritt #2: Wähle ein geeignetes Wort \(x \in L \), mit \(|x| \geq n\), zum "Pumpen".
- Schritt #3: Betrachte alle möglichen Fälle, wie \(x\) in \(u\,v\,w\) aufgeteilt werden kann.
- 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: 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. Wähle das Wort: \[ x ~=~ a^n \, b^n \]Das Wort ist in der Sprache: \( x\in L\). 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\). 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: Fall #2: Der mittlere Wortteil \(v\) besteht nur aus \(b\)-Symbolen: Fall #3: Der mittlere Wortteil \(v\) besteht aus \(a\)- und \(b\)-Symbolen:Schritt #1
Schritt #2
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
Schritt #4
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\).
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\).
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.