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^n{b}^n\mathrm{\mid }n\in \mathbb{N}\}L\; =\; \backslash \{a^nb^n\; ~|~\; n\; \backslash in\; \backslash mathbb\{N\}\backslash \}$ ist nicht regulär. Den Beweis führst du als Widerspruchsbeweis mithilfe des Pumping-Lemmas.

Angenommen, $LL$ ist regulär. Dann gilt das Pumping-Lemma. Sei nun $pp$ die Pumping-Länge und sei $x=a^p{b}^{p}x\; =\; a^pb^p$. Dann gilt

$\mathrm{\mid }x\mathrm{\mid }\ge p|x|\; \backslash ge\; p$

und $xx$ lässt sich somit darstellen als $x=uvwx\; =\; uvw$ mit

$0<\mathrm{\mid }v\mathrm{\mid }\le \mathrm{\mid }uv\mathrm{\mid }\le p0\; \backslash lt\; |v|\; \backslash le\; |uv|\; \backslash le\; p$

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

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

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

Übungsbeispiel

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

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

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

Jetzt musst du nur ein einziges Wort $x\in Lx\; \backslash in\; L$ finden, das lang genug ist, also mindestens so lang wie die Pumping-Länge $pp$, und das einen Anfangsteil $uvuv$ enthält, der kurz genug ist, also höchstens so lang ist wie die Pumping-Länge $pp$, und das so beschaffen ist, dass du in $uvuv$ einen Teil $vv$ "aufpumpen" kannst, um Wörter zu erhalten, die nicht zu $LL$ 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 $LL$ die Sprache aller Wörter gerader Länge über dem Alphabet $AA$ = {a, b}, die du vorwärts und rückwärts lesen kannst, also

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

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

Findest du ein geeignetes Wort $x\in Lx\; \backslash in\; L$?