Pumping-Lemma

Das Pumping-Lemma (englisch to pump = aufpumpen), auch uvw-Theorem, Schleifenlemma, Iterationslemma, Lemma von Bar-Hillel, ist ein Hilfsmittel, um von einer Sprache nachzuweisen, dass sie nicht regulär bzw. nicht kontextfrei ist.

Inhaltsverzeichnis
1 Idee
2 Reguläre Sprachen

2.1 Definition
2.2 Beispiel

3 Kontextfreie Sprachen

3.1 Definition
3.2 Beispiel

Idee

Das Pumping-Lemma liefert lediglich eine notwendige Bedingung dafür, dass eine Sprache regulär ist. Eine notwendige und hinreichende Bedingung liefert der Satz von Myhill-Nerode.

Man unterscheidet zwei Varianten des Pumping-Lemmas. Eine Variante bezieht sich auf reguläre Sprachen, eine andere auf kontextfreie Sprachen.

Reguläre Sprachen

Definition

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

  1. \left| v \right| \ge 1
  2. \left| uv \right| \le n
  3. \forall i \in \mathbb{N}: uv^iw \in L

Beispiel

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

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

Man betrachte nun speziell das Wort x = uvw = anbn.

Gemäß Bedingung 1 ist v nicht leer, gemäß Bedingung 2 besteht v ausschießlich aus as. Mit Bedingung 3 müsste das Wort uv^2w = 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 as als bs. Damit gilt: L ist nicht regulär.

Kontextfreie Sprachen

Definition

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

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

Beispiel

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

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

Wir betrachten das Wort z = anbncn. Es muss dann eine Zerlegung z = uvwxy geben, so dass \left| vx \right| \ge 1, \left| vwx \right| \le n, uv^iwx^iy \in L für alle i \ge 0 ist. Da \left| vwx \right| \le n, enthält das Wort vwx höchstens zwei verschiedene Buchstaben. Da \left| vx \right| \ge 1, kann uv2wx2y nicht von allen drei Buchstaben gleich viele enthalten. Also ist L nicht kontextfrei.
Beim Beweis 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.


Kategorie:Theoretische Informatik Kategorie:Compilerbau

See also: Pumping-Lemma, Formale Sprache, Kontextfreie Sprache, Reguläre Sprache, Satz von Myhill-Nerode