Pumping-Lemma

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

Seinen Namen hat das Lemma vom englischen Begriff to pump, zu deutsch aufpumpen. Es 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 kontextsensitiven Sprachen ermöglichen jedoch kein Pumping-Lemma.

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

Reguläre Sprachen

Pumping-Lemma für reguläre Sprachen

Für jede reguläre Sprache ${\displaystyle L}$ gibt es eine natürliche Zahl ${\displaystyle n}$, sodass gilt: Jedes Wort ${\displaystyle z}$ in ${\displaystyle L}$ mit Mindestlänge ${\displaystyle n}$ hat eine Zerlegung ${\displaystyle z=uvw}$ mit den folgenden drei Eigenschaften:

1. Die beiden Wörter ${\displaystyle u}$ und ${\displaystyle v}$ haben zusammen höchstens die Länge ${\displaystyle n}$.
2. Das Wort ${\displaystyle v}$ ist nicht leer.
3. Für jede natürliche Zahl (mit 0) ${\displaystyle i}$ ist das Wort ${\displaystyle uv^{i}w}$ in der Sprache ${\displaystyle L}$, d. h. die Wörter ${\displaystyle uw}$, ${\displaystyle uvw}$, ${\displaystyle uvvw}$, ${\displaystyle uvvvw}$ usw. sind alle in der Sprache ${\displaystyle L}$.

Das kleinste ${\displaystyle n}$, das diese Eigenschaften erfüllt, wird Pumping-Zahl der Sprache ${\displaystyle L}$ genannt.^[1]

Neben den regulären Sprachen gibt es auch nicht-reguläre Sprachen, die dieses Lemma erfüllen. Eine notwendige und hinreichende Bedingung für reguläre Sprachen liefern der Satz von Myhill-Nerode oder Jaffes Pumping-Lemma.

Das Pumping-Lemma enthält mehrere Wechsel zwischen universeller und existentieller Quantifizierung. Diese kann man gut anhand der folgenden formalen Formulierung des Lemmas erkennen. Darin bezeichnet ${\displaystyle {\mathcal {L}}_{3}}$ die Menge aller regulärer Sprachen.

${\displaystyle {\begin{aligned}\forall L\in {\mathcal {L}}_{3}.\,\exists n\in \mathbb {N} .\,\forall z\in L.\,|z|\geq n\implies \exists u,v,w.\ \ &z=u\circ v\circ w\ \land \\&|uv|\leq n\ \land \\&|v|>0\ \land \\&\forall i\in \mathbb {N} _{0}.\,u\circ v^{i}\circ w\in L\end{aligned}}}$

Beweis

Die Gültigkeit des Lemmas basiert darauf, dass es zu jeder regulären Sprache einen deterministischen endlichen Automaten gibt, der die Sprache akzeptiert. Über einem endlichen Alphabet enthält eine reguläre Sprache mit unendlich vielen Wörtern auch solche Wörter, die mehr Zeichen enthalten als der Automat Zustände hat. Zum Akzeptieren solcher Wörter muss der Automat also einen Zyklus enthalten, der dann in beliebiger Häufigkeit durchlaufen werden kann. Die Buchstabenfolge, die beim Durchlaufen des Zyklus gelesen wird, kann also entsprechend beliebig oft in Wörtern der Sprache vorkommen.

Die Idee des Pumping-Lemmas ist, dass ein Wortteil durch einen Zyklus im deterministischen endlichen Automaten beliebig oft wiederholt werden kann.

Der folgende Beweis setzt die Mindestlänge ${\displaystyle n}$ aus dem Lemma mit der Anzahl der Zustände des Automaten gleich und zeigt, dass wegen der Existenz eines Zyklus jedes Wort mit dieser Mindestlänge die geforderte Zerlegung besitzt.

Sei ${\displaystyle L}$ eine reguläre Sprache. Ist ${\displaystyle L}$ endlich, dann gibt es ein Wort mit maximaler Länge ${\displaystyle k}$. Sei ${\displaystyle n=k+1}$, so ist für alle ${\displaystyle z\in L}$ die Prämisse ${\displaystyle |z|\geq n}$ falsch und die Implikation damit wahr.

Ist ${\displaystyle L}$ unendlich, dann sei ${\displaystyle M}$ ein deterministischer endlicher Automat, der ${\displaystyle L}$ akzeptiert. Da ${\displaystyle L}$ regulär ist, existiert ein solcher Automat ${\displaystyle M}$ immer. Sei ${\displaystyle n}$ die Anzahl der Zustände dieses Automaten, und sei ${\displaystyle z}$ ein beliebiges Wort aus ${\displaystyle L}$ mit mindestens ${\displaystyle n}$ Zeichen. Bezeichne nun mit ${\displaystyle q_{1}\to \dots \to q_{k}}$ die Zustandsfolge, die ${\displaystyle M}$ beim Lesen von ${\displaystyle z}$ beginnend mit dem Startzustand ${\displaystyle q_{1}}$ durchläuft. Da ${\displaystyle z}$ in ${\displaystyle L}$ ist, muss ${\displaystyle z}$ von ${\displaystyle M}$ akzeptiert werden, d. h. ${\displaystyle q_{k}}$ muss ein akzeptierender Zustand sein. Da der Automat ${\displaystyle M}$ gerade ${\displaystyle n}$ Zustände hat, muss spätestens nach dem Lesen von ${\displaystyle n}$ Zeichen eine Zustandswiederholung eintreten. Das heißt, es existieren ${\displaystyle i,j\in \{1,\dots ,n+1\}}$ mit ${\displaystyle i\neq j}$ und ${\displaystyle q_{i}=q_{j}}$. Der Automat ${\displaystyle M}$ durchläuft beim Lesen von ${\displaystyle z}$ also einen Zyklus.

Sei ${\displaystyle v}$ der Teil von ${\displaystyle z}$, der beim Durchlaufen des Zyklus ${\displaystyle q_{i}\to \dots \to q_{j}}$ gelesen wird. Ferner sei ${\displaystyle u}$ der Teil von ${\displaystyle z}$, der beim Durchlaufen der davor liegenden Zustandsfolge ${\displaystyle q_{1}\to \dots \to q_{i}}$ gelesen wird, und ${\displaystyle w}$ sei der Teil von ${\displaystyle z}$, der beim Durchlaufen der dahinter liegenden Zustandsfolge ${\displaystyle q_{j}\to \dots \to q_{k}}$ gelesen wird. Mit dieser Wahl gilt ${\displaystyle z=uvw}$.

Mit dieser Wahl von ${\displaystyle u}$, ${\displaystyle v}$ und ${\displaystyle w}$ gelten die Aussagen aus dem Pumping-Lemma:

1. Die Länge von ${\displaystyle uv}$ ist ${\displaystyle j-1}$ und somit nicht größer als ${\displaystyle n}$.
2. Das Wort ${\displaystyle v}$ ist nicht leer, da ${\displaystyle i\neq j}$ gilt, so dass beim Durchlauf des Zyklus mindestens ein Zeichen gelesen wird.
3. Für beliebiges ${\displaystyle m\geq 0}$ durchläuft der Automat beim Lesen des Worts ${\displaystyle uv^{m}w}$ zunächst die Zustandsfolge ${\displaystyle q_{1}\to \dots \to q_{i}}$, dann ${\displaystyle m}$-mal den Zyklus ${\displaystyle q_{i}\to \dots \to q_{j}}$ und schließlich die Zustandsfolge ${\displaystyle q_{j}\to \dots \to q_{k}}$. Am Ende befindet sich der Automat im akzeptierenden Zustand ${\displaystyle q_{k}}$. Somit gilt ${\displaystyle uv^{m}w\in L}$ für alle ${\displaystyle m\geq 0}$.

Beispiel

Ist die Sprache ${\displaystyle L=\left\{a^{m}b^{m}\mid m\geq 1\right\}}$ regulär?

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

Insbesondere gibt es eine Zerlegung ${\displaystyle uvw}$ mit den beschriebenen Eigenschaften für das Wort ${\displaystyle a^{n}b^{n}\in L}$. Da ${\displaystyle uv}$ ein Präfix dieses Wortes ist und gemäß Eigenschaft 1 höchstens Länge ${\displaystyle n}$ hat, besteht ${\displaystyle uv}$ und damit ${\displaystyle v}$ ausschließlich aus Buchstaben ${\displaystyle a}$. Gemäß Eigenschaft 3 (für ${\displaystyle i=2}$) muss auch das Wort ${\displaystyle uv^{2}w=a^{n+\left|v\right|}b^{n}}$ in ${\displaystyle L}$ liegen. Da aber ${\displaystyle \left|v\right|>0}$ (Eigenschaft 2), enthält dieses Wort mehr ${\displaystyle a}$ als ${\displaystyle b}$, liegt also nicht in ${\displaystyle L}$.

Also führt die Annahme, ${\displaystyle L}$ sei eine reguläre Sprache, zum Widerspruch und ist damit falsch.

Eine nicht-reguläre Sprache, die den Bedingungen des Pumping-Lemmas genügt

Die Sprache ${\displaystyle L=\left\{a^{m}b^{n}c^{n}\mid m,n\geq 1\right\}\cup \{b^{m}c^{n}\mid m,n\geq 0\}}$ ist nicht regulär. Allerdings erfüllt ${\displaystyle L}$ die Eigenschaften des Pumping-Lemmas, denn jedes Wort ${\displaystyle z\in L}$ lässt sich so zerlegen ${\displaystyle z=uvw}$, dass auch für alle ${\displaystyle i\geq 0}$ ${\displaystyle uv^{i}w\in L}$. Dazu kann ${\displaystyle v}$ einfach als erster Buchstabe gewählt werden. Dieser ist entweder ein ${\displaystyle a}$, die Anzahl von führenden ${\displaystyle a}$s ist beliebig. Oder er ist ein ${\displaystyle b}$ oder ${\displaystyle c}$, ohne führende ${\displaystyle a}$s ist aber die Anzahl von führenden ${\displaystyle b}$s oder ${\displaystyle c}$s beliebig.

Jaffes Pumping-Lemma

Jeffrey Jaffe hat ein verallgemeinertes Pumping-Lemma entwickelt,^[2] das äquivalent zur Definition der regulären Sprachen ist. Es ist also eine notwendige und hinreichende Bedingung zum Nachweis der Regularität einer Sprache.

Die Sprache ${\displaystyle L\subseteq \Sigma ^{*}}$ ist regulär genau dann, wenn eine Konstante ${\displaystyle n>0,n\in \mathbb {N} }$ existiert, so dass es für alle ${\displaystyle z\in \Sigma ^{*}}$, ${\displaystyle |z|=n}$ eine Zerteilung ${\displaystyle z=uvw}$ mit ${\displaystyle u,w\in \Sigma ^{*},v\in \Sigma ^{+}}$ gibt, so dass für alle ${\displaystyle i\geq 0}$ und Suffixe ${\displaystyle x\in \Sigma ^{*}}$ gilt:

${\displaystyle zx\in L\iff uv^{i}wx\in L}$.

Kontextfreie Sprachen

Pumping-Lemma für kontextfreie Sprachen

Für jede kontextfreie Sprache ${\displaystyle L}$ gibt es eine natürliche Zahl ${\displaystyle n}$, sodass gilt: Jedes Wort ${\displaystyle z}$ in ${\displaystyle L}$ mit Mindestlänge ${\displaystyle n}$ hat eine Zerlegung ${\displaystyle z=uvwxy}$ mit den folgenden drei Eigenschaften:

1. Die Wörter ${\displaystyle v}$, ${\displaystyle w}$ und ${\displaystyle x}$ haben zusammen höchstens die Länge ${\displaystyle n}$, d. h. ${\displaystyle |vwx|\leq n}$.
2. Eines der Wörter ${\displaystyle v}$, ${\displaystyle x}$ ist nicht leer. Also ${\displaystyle |vx|\geq 1}$.
3. Für jede natürliche Zahl (mit 0) ${\displaystyle i}$ ist das Wort ${\displaystyle uv^{i}wx^{i}y}$ in der Sprache ${\displaystyle L}$, d. h. die Wörter ${\displaystyle uwy}$, ${\displaystyle uvwxy}$, ${\displaystyle uvvwxxy}$ usw. liegen alle in ${\displaystyle L}$.

Neben den kontextfreien Sprachen gibt es auch nicht kontextfreie Sprachen, die dieses Pumping-Lemma erfüllen. Die Umkehrung des Lemmas gilt im Allgemeinen also nicht. Eine Verallgemeinerung des Pumping-Lemmas für kontextfreie Sprachen ist Ogdens Lemma.

Beweis

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

Die Idee des Pumping-Lemmas für kontextfreie Sprachen ist, dass ein Wortteil durch mehrfaches Ableiten derselben Variablen beliebig oft wiederholt werden kann.

Betrachten wir nun einen Ableitungsbaum T für ${\displaystyle 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 ${\displaystyle h\geq \log(n)=\left|N\right|}$. Es gibt also einen Pfad ${\displaystyle v_{0}\ldots v_{h}}$ in T von der Wurzel zu einem Blatt, für den gilt, dass er Länge ${\displaystyle h+1>\left|N\right|}$ hat. Es existieren also zwei Knoten ${\displaystyle v_{j},v_{k}}$ auf diesem Pfad mit ${\displaystyle 0\leq j<k\leq h}$, welche die gleichen Variablen von G ${\displaystyle A_{j},A_{k}}$ repräsentieren.

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

Beispiel

Das Wort ${\displaystyle vwx}$ enthält höchstens zwei verschiedene Buchstaben.

Ist die Sprache ${\displaystyle L=\left\{a^{m}b^{m}c^{m}\mid m\geq 1\right\}}$ kontextfrei?

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

Wir betrachten das Wort ${\displaystyle z=a^{n}b^{n}c^{n}}$. Es muss dann eine Zerlegung ${\displaystyle z=uvwxy}$ geben, so dass ${\displaystyle \left|vx\right|\geq 1}$, ${\displaystyle \left|vwx\right|\leq n}$, ${\displaystyle uv^{i}wx^{i}y\in L}$ für alle ${\displaystyle i\geq 0}$ ist. Da ${\displaystyle \left|vwx\right|\leq n}$, enthält das Wort ${\displaystyle vwx}$ höchstens zwei verschiedene Buchstaben. Deshalb, und da ${\displaystyle \left|vx\right|\geq 1}$ gilt, enthält ${\displaystyle uv^{2}wx^{2}y}$ nicht von allen drei Buchstaben gleich viele, ist also nicht in ${\displaystyle L}$ enthalten. Das ist ein Widerspruch; die Annahme, ${\displaystyle L}$ sei kontextfrei, ist also falsch.

Eine nicht-kontextfreie Sprache, die dem Pumping-Lemma genügt

Die Sprachen ${\displaystyle L_{1}=\{\$^{+}(a^{n}b^{n})^{n}|n\in \mathbb {N} \}}$ und ${\displaystyle L_{2}=\left\{a^{k}b^{l}c^{m}d^{n}\mid k,l,m,n\in \mathbb {N} :k=0{\text{ oder }}l=m=n\right\}}$ sind nicht kontextfrei. Allerdings erfüllen ${\displaystyle L_{1}}$ und ${\displaystyle L_{2}}$ die Eigenschaften des Pumping-Lemmas: Enthält ein Wort ${\displaystyle z\in L_{2}}$ nicht den Buchstaben ${\displaystyle a}$, so gilt dies auch für alle Wörter ${\displaystyle uv^{i}wx^{i}y}$. Ist der Buchstabe ${\displaystyle a}$ hingegen enthalten, gibt es eine Zerlegung mit ${\displaystyle u=v=w=\varepsilon }$ (${\displaystyle \varepsilon }$ bezeichne das leere Wort), ${\displaystyle x=a}$ und einem Suffix ${\displaystyle y}$, sodass abermals alle Wörter ${\displaystyle uv^{i}wx^{i}y}$ in ${\displaystyle L_{2}}$ enthalten sind. Für ${\displaystyle L_{1}}$lässt sich ${\displaystyle v=\$}$ und ${\displaystyle x=\varepsilon }$ wählen, und damit ist ${\displaystyle uv^{i}wx^{i}y}$ in ${\displaystyle L_{1}}$ enthalten.

Einzelnachweise

1. ↑ Skript (PDF; 1,1 MB) Humboldt-Universität Berlin
2. ↑ Jeffrey Jaffe: A necessary and sufficient pumping lemma for regular languages. doi:10.1145/990524.990528