Das Pumping-Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen läßt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei ist.

Ihren Namen hat das Lemma vom englischen Begriff to pump, zu deutsch aufpumpen. Er leitet sich davon ab, dass Teile von Wörtern aus Sprachen bestimmter Klassen vervielfacht (aufgepumpt) werden können, so dass die dabei entstehenden Wörter ebenfalls in der Sprache sind.

Man unterscheidet zunächst zwischen dem Pumping-Lemma für reguläre Sprachen und jenem für kontextfreie Sprachen. In der Literatur sind weiterhin Pumping-Lemmata für Erweiterungen der kontextfreien Sprachen anzutreffen. Mächtigere Sprachklassen in der Chomsky-Hierarchie wie die kontextsensitiven Sprachen und auch die wachsend kontextsensitive Sprachen ermöglichen jedoch kein Pumpinglemma.

Alternativ wird das Lemma bzw. seine Ausprägungen auch als uvw-Theorem, uvwxy-Theorem, Schleifenlemma, Iterationslemma oder Lemma von Bar-Hillel bezeichnet.

Variante 1: Das Pumping-Lemma für reguläre Sprachen

---

Annahmen

Sei $\backslash mathcal\{L\}\_3$ die Menge der regulären Sprachen. Zur Erzeugung einer regulären Sprache gibt es eine Grammatik des Chomsky-Hierarchie-Typ 3.

Aussage des Pumping-Lemmas für reguläre Sprachen

Sei $L$ eine reguläre Sprache, also $L\; \backslash in\; \backslash mathcal\{L\}\_3$ . Dann gibt es eine natürliche Zahl $n\; \backslash in\; \backslash mathbb\{N\}$, sodass sich alle Wörter $x\; \backslash in\; L$ mit $\backslash left|\; x\; \backslash right|\; \backslash ge\; n$ in $x\; =\; uvw$ zerlegen lassen, wobei gilt:

1. $\backslash left|\; v\; \backslash right|\; \backslash ge\; 1$
2. $\backslash left|\; uv\; \backslash right|\; \backslash le\; n$
3. $\backslash forall\; i\; \backslash ge\; 0\; :\; uv^iw\; \backslash in\; L$

Nicht jede Sprache die dieses Lemma erfüllt ist regulär. Eine notwendige und hinreichende Bedingung für reguläre Sprachen liefern der Satz von Myhill-Nerode oder Jaffes Pumping-Lemma (s.u.).

Korrektheitsbeweis

Falls L endlich ist, so existiert eine obere Schranke für die Länge der Wörter aus L. Es existiert also eine natürliche Zahl n ∈ N, für die gilt: |x| < n ∀ x ∈ L. Umgekehrt gilt, dass die Menge aller Wörter aus L, die länger als n sind, eine leere Menge ist: L' := {x ∈ L | |x| ≥ n} = ø. Da für leere Mengen Aussagen der Form „für alle Elemente der Menge gilt…“ trivialerweise immer erfüllt sind, ist auch die Behauptung für dieses n trivialerweise erfüllt. Das Pumping-Lemma ist also trivial, falls L endlich ist.

Sei daher L ohne Beschränkung der Allgemeinheit unendlich, das heißt, es existiert keine obere Schranke für die Länge der Wörter aus L. Oder anders formuliert: Für jedes Wort aus L findet sich immer ein anderes Wort aus L, das noch länger ist.

Pumping-Lemma.png

Da L regulär ist, existiert ein deterministischer endlicher Automat M, der L akzeptiert. Sei n := |M| die Anzahl der Zustände dieses Automaten. Weiter sei x ∈ L ein beliebiges Wort aus L mit mehr als n Zeichen, also |x| > n. Die Existenz eines solchen Wortes wurde im vorherigen Abschnitt sichergestellt.

Ohne Beschränkung der Allgemeinheit durchlaufe M auf x die Zustandsfolge q₁→...→q_k, wobei q_k der akzeptierende Endzustand sei. Da M weniger Zustände hat als x Zeichen enthält, durchläuft M auf x mindestens einen Zustand mehr als einmal, das heißt es existieren i ≠ j ∈ {1, ..., k} mit q_i = q_j. M durchläuft auf x also einen Zyklus.

Sei v der Teil von x, der durch Durchlaufen des Zyklus q_i→...→q_j entsteht. Ferner sei u der Teil von x, der durch die davor liegende Zustandsfolge q₁→...→q_i entsteht, w sei der Teil, der durch die dahinter liegende Zustandsfolge q_j→...→q_k entsteht. Es gilt also x = uvw. Für alle n ≥ |M| ist nun das Pumping-Lemma erfüllt:

1. Der erste Teil der Behauptung folgt direkt aus der Existenz des Zyklus. Da ein Zyklus aus mindestens einer Kante besteht und für jede Kante ein Zeichen hinzugefügt wird, gilt |v| ≥ 1.
2. Der zweite Teil der Behauptung folgt trivial aus der Wahl der Konstante n. Dadurch, dass n größer oder gleich der Anzahl der Zustände von M ist, kann |uv| unmöglich größer als n sein. Es ist allerdings durchaus möglich, dass u oder w leer sind.
3. Durch wiederholtes Durchlaufen des Zyklus entstehen die Wörter uvvw, uvvvw, ..., uvⁱw mit beliebigem i ≥ 1. Ferner kann der Zyklus auch ganz ausgelassen werden, wodurch das Wort uv⁰w = uw entsteht. Alle diese Wörter sind in L, da der deterministische endliche Automat seine Berechnung stets im akzeptierenden Endzustand beendet. $\backslash Box$

Beispiel

Ist die Sprache $L\; =\; \backslash \{\; a^mb^m\; |\; m\; \backslash ge\; 1\; \backslash \}$ regulär?

Angenommen, $L$ sei eine reguläre Sprache. Dann gibt es gemäß Pumping-Lemma eine Zahl $n$, sodass sich alle Wörter $x\; \backslash in\; L$ mit $\backslash left|\; x\; \backslash right|\; \backslash ge\; n$ wie beschrieben zerlegen lassen.

Man betrachte nun speziell das Wort $x\; =\; uvw\; =\; a^nb^n$.

Gemäß Bedingung 1 ist $v$ nicht leer, gemäß Bedingung 2 besteht $uv$ und somit auch $v$ ausschließlich aus $a$s (da $|uv|\; \backslash leq\; n$ und $|uvw|\; =\; |a^n\; b^n|\; =\; 2n$). Mit Bedingung 3 müsste das Wort $uv^2w\; =\; a^\{n\; -\; \backslash left|\; v\; \backslash right|\}a^\{2\; *\; \backslash left|\; v\; \backslash right|\}b^n\; =\; a^\{n+\; \backslash left|\; v\; \backslash right|\}b^n$ in $L$ liegen. Das ist aber offensichtlich falsch, denn dieses Wort hat mehr $a$s als $b$s. Damit gilt: $L$ ist nicht regulär.

Eine nicht-reguläre Sprache die das Pumping-Lemma erfüllt

Die Sprache $L\; =\; \backslash \{\; a^mb^nc^n\; |\; m,n\; \backslash ge\; 1\; \backslash \}\; \backslash cup\; \backslash \{b^mc^n|m,n\; \backslash ge\; 0\; \backslash \}$ ist nicht regulär; dies ist leicht anhand des obigen Beispiels einzusehen. Allerdings erfüllt $L$ das Pumping-Lemma, denn jedes Wort $x\; \backslash in\; L$ läßt sich so zerlegen $x=\; uvw$, dass auch für alle $i\backslash ge0$ $uv^iw\; \backslash in\; L$. Dazu kann $v$ einfach als erster Buchstabe gewählt werden. Dieser ist entweder ein $a$, die Anzahl von führenden $a$s ist beliebig. Oder er ist ein $b$ oder $c$, ohne führende $a$s ist aber die Anzahl von führenden $b$s oder $c$s beliebig.

Jaffes Pumping-Lemma

Jeffrey Jaffe hat ein verallgemeinertes Pumping-Lemmas entwickelt, das äquivalent zur Definition der regulären Sprachen ist. Es ist also eine hinreichende Bedingung zum Nachweis der Regularität einer Sprache.

Die Sprache $L\; \backslash in\; \backslash Sigma\; ^\{*\}$ ist regulär genau dann wenn eine Konstante $k\; >\; 0\; \backslash in\; \backslash mathbb\{N\}$ existiert so, dass für alle $w\; \backslash in\; \backslash Sigma^\{*\}$ $|w|\; \backslash geq\; k$ gilt: Es gibt eine Zerteilung $x,\; y,\; z\; \backslash in\; \backslash Sigma\; ^\{*\}$ so, dass $\{w\}\; =\; xyz$ $y\; \backslash neq\; \backslash epsilon$, und für alle $i\; \backslash geq\; 0$ und $v\; \backslash in\; \backslash Sigma\; ^\{*\}$ gilt:

$wv\; \backslash in\; L\; \backslash iff\; xy^\{i\}zv\; \backslash in\; L$.

Variante 2: Das Pumping-Lemma für kontextfreie Sprachen

---

Annahmen

Sei $\backslash mathcal\{L\}\_2$ die Klasse aller Sprachen, die von Chomsky-Hierarchie-Typ-2-Grammatiken erzeugt werden. $\backslash mathcal\{L\}\_2$ bezeichnet somit die Klasse der kontextfreien Sprachen.

Aussage des Pumping-Lemmas für kontextfreie Sprachen

Sei $L$ eine kontextfreie Sprache, also in $\backslash mathcal\{L\}\_2$. Dann gibt es eine Konstante $n\; \backslash in\; \backslash mathbb\{N\}$, sodass sich alle Wörter $z\; \backslash in\; L$ mit $\backslash left|\; z\; \backslash right|\; \backslash ge\; n$ in $z\; =\; uvwxy$ zerlegen lassen, sodass gilt:

1. $\backslash left|\; vx\; \backslash right|\; \backslash ge\; 1$
2. $\backslash left|\; vwx\; \backslash right|\; \backslash le\; n$
3. $\backslash forall\; i\; \backslash ge\; 0:\; uv^iwx^iy\; \backslash in\; L$

Eine Verschärfung des Pumping-Lemmas für kontextfreie Sprachen ist Ogdens Lemma.

Korrektheitsbeweis

Gegeben sei eine kontextfreie Grammatik G in Chomsky-Normalform mit N Variablen, für die gilt, dass sie gerade die gewünschte Sprache beschreibt. Sei nun ein Wort $x$ aus dieser Sprache gegeben, für das gilt: $|x|\; \backslash geq\; 2^N\; =\; n$.

Betrachten wir nun einen Ableitungsbaum T für $x$ mit Höhe h. Da unsere Sprache in CNF angegeben wurde, hat T die Form eines Binärbaumes. Daraus folgt für die Höhe von T $h\; \backslash geq\; log(n)\; =\; N$. Es gibt also einen Pfad $v\_0\; ...\; v\_h$ in T von der Wurzel zu einem Blatt, für den gilt, dass er Länge $h+1\; >\; N$ hat. Es existieren also zwei Knoten $v\_j,\; v\_k$ auf diesem Pfad mit , welche die gleichen Variablen von G $A\_j,\; A\_k$ repräsentieren.

Betrachtet man den Teilbaum $T\_k$, welcher von $v\_k$ aus aufgespannt wird, so bilden dessen Blätter den Teilstring $w$. Der Teilbaum $T\_j$, welcher von $v\_j$ aufgespannt wird, besitzt als Teilbaum den Baum $T\_k$. Man kann also die Blätter von $T\_j$ aufteilen in Blätter links von $T\_k$ und Blätter rechts von $T\_k$ und erhält somit eine Aufteilung der Blätter von $T\_j$ der Form $vwx$. Ebenso unterteilt der Teilbaum $T\_j$ den gesamten Ableitungsbaum in drei Teile $u,vwx,\; y$. Wir erhalten also als Aufteilung die Teilstrings $u,\; y$, welche im Ableitungsbaum links bzw. rechts von dem von $v\_j$ aufgespannten Teilbaum liegen, die Teilstrings $v,\; x$, welche in dem Teilbaum $T\_j$ liegen nicht jedoch in $T\_k$, und zu guter Letzt den Teilstring $w$, welcher in $T\_k$ liegt. Da $v\_j$ und $v\_k$ die gleichen Variablen unserer Grammatik repräsentieren, folgt daraus, dass der Pfad von $v\_j$ nach $v\_k$ beliebig oft wiederholt werden kann. Durch eine Wiederholung des Pfades würden wir Worte der Form $uv^iwx^iy$ erzeugen, ohne unsere Sprache zu verlassen. Womit wir das Pumping-Lemma für kontextfreie Sprachen bewiesen hätten.

Beispiel

Ist die Sprache $L\; =\; \backslash \{\; a^mb^mc^m\; |\; m\; \backslash ge\; 1\; \backslash \}$ kontextfrei?

Wir nehmen an, $L$ sei kontextfrei. Sei dann $n$ die zugehörige Konstante aus dem Pumping-Lemma.

Wir betrachten das Wort $z\; =\; a^nb^nc^n$. Es muss dann eine Zerlegung $z\; =\; uvwxy$ geben, sodass $\backslash left|\; vx\; \backslash right|\; \backslash ge\; 1$, $\backslash left|\; vwx\; \backslash right|\; \backslash le\; n$, $uv^iwx^iy\; \backslash in\; L$ für alle $i\; \backslash ge\; 0$ ist. Da $\backslash left|\; vwx\; \backslash right|\; \backslash le\; n$, enthält das Wort $vwx$ höchstens zwei verschiedene Buchstaben. Da $\backslash left|\; vx\; \backslash right|\; \backslash ge\; 1$, kann $uv^2wx^2y$ nicht von allen drei Buchstaben gleich viele enthalten. Also ist $L$ nicht kontextfrei.

Formale Sprachen | Compilerbau

Lemma o vkládání | Pumping lemma | למת הניפוח לשפות חופשיות הקשר | 펌핑 렘마 | 泵引理