Pumping-Lemma

Das Pumping-Lemma ist eine Methode der Theoretischen Informatik, mit der überprüft werden kann, ob sog. formale Sprachen bestimmte Ausprägungen haben. Sie weist ggf. nach, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei (uvwxy-Theorem) ist.

Die Methode wird alternativ als auch uvw-Theorem, Schleifenlemma, Iterationslemma oder Lemma von Bar-Hillel bezeichnet. Ihren Namen hat sie vom englischen Begriff to pump, zu deutsch aufpumpen.

In der Literatur sind Pumping-Lemmata auch für Erweiterungen der kontextfreien Sprachen anzutreffen. Für kontextsensitive und sogar wachsend kontextsensitive Sprachen ist bekannt, dass hier kein Pumping-Lemma möglich ist.

Von Ogden ist das Pumping-Lemma verschärft worden, siehe Ogdens Lemma.

Idee

Das Pumping-Lemma ist eine Methode, um nachzuweisen, ob eine formale Sprache nicht regulär (Variante 1) bzw. nicht kontextfrei (Variante 2) ist. Es liefert für diesen Beweis eine notwendige Bedingung. So wird der Beweis dann als Widerspruchsbeweis geführt. Es wird angenommen, dass eine Sprache regulär oder kontextfrei sei. Diese Aussage wird mit Hilfe eines Pumping-Lemmas zum Widerspruch geführt.

Eine notwendige und hinreichende Bedingung liefert der Satz von Myhill-Nerode.

Variante 1: Prüfung auf Regularität von Sprachen

Annahmen

Sei ${\mathcal {L}}_{3}$ eine Grammatik des Chomsky-Hierarchie-Typ 3. Diese bezeichnet die regulären Sprachen.

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

Sei $L$ eine reguläre Sprache, also $L\in {\mathcal {L}}_{3}$ . Dann gibt es eine Zahl $n\in \mathbb {N}$, sodass sich alle Wörter $x\in L$ mit $\left|x\right|\geq n$ in $x=uvw$ zerlegen lassen, sodass gilt:

1. $\left|v\right|\geq 1$
2. $\left|uv\right|\leq n$
3. $\forall i\in \mathbb {N} :uv^{i}w\in L$

Beispiel

Ist die Sprache $L=\{a^{m}b^{m}|m\geq 1\}$ regulär?

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

Man betrachte nun speziell das Wort $x=uvw=a^{n}b^{n}$.

Gemäß Bedingung 1 ist $v$ nicht leer, gemäß Bedingung 2 besteht $uv$ und somit auch $v$ ausschließlich aus $a$s (da $|uv|\leq n$ und $|uvw|=|a^{n}b^{n}|=2n$). Mit Bedingung 3 müsste das Wort $uv^{2}w=a^{m-\left|v\right|}a^{2*\left|v\right|}b^{m}=a^{m+\left|v\right|}b^{m}$ 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.

Variante 2: Prüfung auf Kontextfreiheit von Sprachen

Annahmen

Sei ${\mathcal {L}}_{2}$ eine Chomsky-Hierarchie-Typ-2-Grammatik. Diese bezeichnet die kontextfreien Sprachen.

Aussage des Pumping-Lemmas für kontextfreie Sprachen

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

1. $\left|vx\right|\geq 1$
2. $\left|vwx\right|\leq n$
3. $\forall i\geq 0:uv^{i}wx^{i}y\in L$

Beispiel

Ist die Sprache $L=\{a^{m}b^{m}c^{m}|m\geq 1\}$ kontextfrei?

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

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

Beim Beweis sollte man am Besten folgende Fälle betrachten:

1. $v$ oder $x$ enthalten verschiedene Buchstabensorten.
2. $v$ und $x$ enthalten die gleiche Buchstabensorte.
3. $v$ und $x$ enthalten die gleiche Buchstabensorte und eins von beiden ist leer.