Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Das Pumping-Lemma für reguläre Sprachen

Das Pumping-Lemma für reguläre Sprachen benutzt du, um zu zeigen, dass eine bestimmte Sprache nicht regulär ist. Die Bezeichnung Pumping deutet darauf hin, dass genügend lange Wörter einer regulären Sprache sich an einer Stelle "aufpumpen" lassen. Ein Lemma ist ein Hilfssatz, der für Beweise nützlich ist.

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

SatzPumping-Lemma

Sei A ein Alphabet und LA eine reguläre Sprache. Dann lassen sich alle Wörter xL ab einer gewissen Länge |x|p (der Pumping-Länge) zerlegen in

x=uvw  mit   u,v,wA und 0<|v||uv|p

sodass gilt

uvkwL für alle k0.

Jedes Wort x ab einer gewissen Länge p (der Pumping-Länge) enthält also ein Teilwort v, mit dem sich das Wort x "aufpumpen" lässt – daher die Bezeichnung Pumping-Lemma. Die Wörter, die durch das Aufpumpen entstehen, sind ebenfalls Elemente der Sprache L.

Pumping-Lemma anwenden

Die Sprache L={anbn | 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=apbp. Dann gilt

|x|p

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

0<|v||uv|p

Da |uv|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 uv2w=ap+rbpL, 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 xL finden, das lang genug ist, d.h. mit |x|p, und ein Anfangswort uv von x, das kurz genug ist, d.h. mit |uv|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 = { ε, 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 xL 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  = { ε, 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 xL?

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?