Das Pumping-Lemma für reguläre Sprachen

Die Formulierung des Pumping-Lemmas ist etwas technisch. Aber dafür ist es in der Anwendung grandios.

Pumping-Lemma anwenden

Die Sprache $L = \{a^nb^n ~|~ n \in \mathbb{N}\}$ ist nicht regulär. Den Beweis führst du als Widerspruchsbeweis mithilfe des Pumping-Lemmas.

Angenommen, $L$ ist regulär. Dann gilt das Pumping-Lemma. Sei nun $p$ die Pumping-Länge und sei $x = a^pb^p$. Dann gilt

$|x| \ge p$

und $x$ lässt sich somit darstellen als $x = uvw$ mit

$0 \lt |v| \le |uv| \le p$

Da $|uv| \le p$, besteht $uv$ nur aus a's, und damit besteht auch $v$ nur aus a's. Sei $r$ die Länge von $v$; es gilt $r > 0$. Dann ist nach dem Pumping-Lemma auch $uv^2w = a^{p+r}b^p \in L$, im Widerspruch zur Definition von $L$. Also ist die Annahme falsch, $L$ ist also nicht regulär.

Die Anwendung des Pumping-Lemmas verläuft immer nach diesem Schema. Du nimmst an, dass $L$ regulär ist. Dann gilt das Pumping-Lemma, und es gibt somit eine Pumping-Länge $p$. Jetzt musst du nur ein einziges Wort $x \in L$ finden, das lang genug ist, d.h. mit $|x| \ge p$, und ein Anfangswort $uv$ von $x$, das kurz genug ist, d.h. mit $|uv| \le p$, und das so beschaffen ist, dass du in $uv$ einen Teil $v$ "aufpumpen" kannst, um Wörter zu erhalten, die nicht in $L$ liegen. Damit erhältst du einen Widerspruch zur Annahme, dass $L$ regulär ist.

In obigem Beweis hast du dafür gesorgt, dass $uv$ nur aus a's besteht. Somit besteht auch das Teilwort $v$ nur aus a's, ganz gleich, welchen Teil von $uv$ es einnimmt. Wird nun $v$ "aufgepumpt", so entstehen Wörter mit mehr a's als b's, also Wörter, die nicht zu $L$ gehören. Damit kann $L$ nicht regulär sein.

Übungsbeispiel

Versuche es einmal selbst. Zeige, dass die Sprache $L$ aller Wörter über dem Alphabet $A$ = {a,b}, die gleich viele a's und b's enthalten, nicht regulär ist.

$L$ = { $\varepsilon$, ab, ba, aabb, abab, abba, baab, baba, bbaa, …}

Beginne deinen Beweis mit den Worten: "Angenommen, die Sprache $L$ ist regulär. Dann gilt das Pumping-Lemma. Sei nun $p$ die Pumping-Länge und sei $x$ = … "

Jetzt musst du nur ein einziges Wort $x \in L$ finden, das lang genug ist, also mindestens so lang wie die Pumping-Länge $p$, und das einen Anfangsteil $uv$ enthält, der kurz genug ist, also höchstens so lang ist wie die Pumping-Länge $p$, und das so beschaffen ist, dass du in $uv$ einen Teil $v$ "aufpumpen" kannst, um Wörter zu erhalten, die nicht zu $L$ gehören.

Du kennst ein solches Wort schon, deswegen ist diese Aufgabe ein bisschen zu leicht. Also schau dir noch einmal die folgende, nicht viel schwerere Aufgabe an.

Sei $L$ die Sprache aller Wörter gerader Länge über dem Alphabet $A$ = {a, b}, die du vorwärts und rückwärts lesen kannst, also

$L$  = { $\varepsilon$, aa, bb, aaaa, abba, baab, bbbb, aaaaaa, aabbaa, abaaba, baaaab, abbbba, ...}

Zeige, dass die Sprache $L$ nicht regulär ist. Beginne deinen Beweis mit den Worten: "Angenommen, die Sprache L ist regulär. Dann gilt das Pumping-Lemma. Sei nun $p$ die Pumping-Länge und sei $x$ = … "

Findest du ein geeignetes Wort $x \in L$?