Wikipedia · einfach zusammengefasst · Stand
Pumping-Lemma
Pumplemma (auch Schleifensatz genannt) beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. ... sei eine reguläre …
Inhalt6 Abschnitte
Grundidee und Zweck
Das Pumping-Lemma, auch Pumplemma oder Schleifensatz genannt, beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet. Das Lemma ist wichtig, weil man damit in vielen Fällen zeigen kann, dass eine Sprache nicht regulär oder nicht kontextfrei ist.
Die Grundidee lautet: In Wörtern bestimmter Sprachklassen gibt es ab einer gewissen Mindestlänge einen Teil, der wiederholt oder weggelassen werden kann, ohne die Sprache zu verlassen. Dieses Wiederholen heißt „pumpen“. Man unterscheidet vor allem das Pumping-Lemma für reguläre Sprachen und das Pumping-Lemma für kontextfreie Sprachen.
Das Pumping-Lemma ist dabei nur eine notwendige Bedingung: Jede reguläre Sprache erfüllt das Pumping-Lemma für reguläre Sprachen, aber nicht jede Sprache, die dieses Lemma erfüllt, ist regulär. Entsprechend gilt für kontextfreie Sprachen: Jede kontextfreie Sprache erfüllt ihr Pumping-Lemma, aber es gibt auch nicht-kontextfreie Sprachen, die es erfüllen. Für mächtigere Sprachklassen der Chomsky-Hierarchie wie kontextsensitive Sprachen und wachsend kontextsensitive Sprachen gibt es kein Pumping-Lemma.
Reguläre Sprachen
Für jede reguläre Sprache L gibt es eine natürliche Zahl n, sodass jedes Wort z in L mit mindestens n Zeichen eine Zerlegung z = uvw besitzt. Diese Zerlegung muss drei Bedingungen erfüllen:
- Die Wörter u und v haben zusammen höchstens die Länge n, also |uv| ≤ n.
- Das Wort v ist nicht leer, also |v| > 0.
- Für jede natürliche Zahl mit 0, also i ∈ ℕ₀, liegt uv^i w wieder in L. Das bedeutet: uw, uvw, uvvw, uvvvw usw. gehören alle zur Sprache.
Das kleinste n, das diese Eigenschaften erfüllt, heißt Pumping-Zahl der Sprache L.
Die formale Aussage enthält mehrere Wechsel zwischen „für alle“ und „es gibt“. Sie lautet sinngemäß: Für jede reguläre Sprache L gibt es ein n, sodass für jedes lange genug gewählte Wort z aus L eine passende Zerlegung u, v, w existiert, mit der jedes aufgepumpte Wort uv^i w wieder in L liegt.
Das Lemma eignet sich besonders für Widerspruchsbeweise: Man nimmt an, eine Sprache sei regulär, verwendet dann die garantierte Zerlegung und zeigt, dass ein aufgepumptes Wort doch nicht mehr in der Sprache liegen kann. Damit ist die Annahme widerlegt. Eine notwendige und hinreichende Bedingung für Regularität liefern dagegen der Satz von Myhill-Nerode oder Jaffes Pumping-Lemma.
Warum das reguläre Lemma gilt
Die Begründung für das Pumping-Lemma regulärer Sprachen beruht auf deterministischen endlichen Automaten. Zu jeder regulären Sprache gibt es einen solchen Automaten, der genau diese Sprache akzeptiert. Ein deterministischer endlicher Automat hat nur endlich viele Zustände.
Wenn eine reguläre Sprache endlich ist, kann man n als eine Zahl wählen, die größer ist als die Länge des längsten Wortes der Sprache. Dann gibt es gar kein Wort z ∈ L mit |z| ≥ n; die Aussage des Lemmas ist dadurch automatisch erfüllt.
Ist L unendlich, sei M ein deterministischer endlicher Automat für L und n die Anzahl seiner Zustände. Liest M ein Wort z ∈ L mit mindestens n Zeichen, muss beim Durchlaufen der Zustände spätestens nach n Zeichen ein Zustand wiederholt werden. Dadurch entsteht ein Zyklus. Der Teil des Wortes, der vor dem Zyklus gelesen wird, heißt u; der Teil, der während des Zyklus gelesen wird, heißt v; der Rest heißt w. Damit gilt z = uvw.
Weil der Zyklus mindestens ein Zeichen liest, ist v nicht leer. Weil die Wiederholung spätestens innerhalb der ersten n gelesenen Zeichen auftritt, gilt |uv| ≤ n. Da der Automat denselben Zyklus beliebig oft durchlaufen kann und danach wieder in denselben weiteren Verlauf kommt, akzeptiert er jedes Wort uv^m w für m ≥ 0. Deshalb bleiben alle aufgepumpten Wörter in L.
Typische Anwendung bei regulären Sprachen
Ein Standardbeispiel ist die Sprache L = {a^m b^m | m ≥ 1}. Sie enthält Wörter mit gleich vielen a und b, zuerst alle a, danach alle b. Mit dem Pumping-Lemma lässt sich zeigen, dass diese Sprache nicht regulär ist.
Man nimmt zum Widerspruch an, L sei regulär. Dann gibt es eine Pumping-Zahl n. Das Wort a^n b^n liegt in L und ist lang genug. Nach dem Pumping-Lemma muss es eine Zerlegung a^n b^n = uvw geben, bei der |uv| ≤ n und |v| > 0 gilt. Da die ersten n Zeichen alle a sind, besteht v nur aus a.
Für i = 2 müsste dann auch uv^2 w in L liegen. Dieses Wort hat aber mehr a als b, nämlich a^(n+|v|) b^n. Weil |v| > 0 ist, sind die Anzahlen der a und b nicht mehr gleich. Das Wort liegt also nicht in L. Das widerspricht dem Pumping-Lemma; deshalb ist L nicht regulär.
Der Artikel nennt außerdem eine nicht-reguläre Sprache, die trotzdem die Bedingungen des Pumping-Lemmas erfüllt: L = {a^m b^n c^n | m,n ≥ 1} ∪ {b^m c^n | m,n ≥ 0}. Sie erfüllt die Eigenschaften schon mit n = 1, ist aber nicht regulär. Das zeigt, dass das Pumping-Lemma allein keine vollständige Charakterisierung regulärer Sprachen ist.
Jaffes Kriterium
Jeffrey Jaffe entwickelte ein verallgemeinertes Pumping-Lemma, das äquivalent zur Definition regulärer Sprachen ist. Es ist damit nicht nur notwendig, sondern auch hinreichend: Eine Sprache ist genau dann regulär, wenn sie Jaffes Bedingung erfüllt.
Für eine Sprache L ⊆ Σ* gilt: L ist regulär genau dann, wenn eine Konstante n > 0 mit n ∈ ℕ existiert, sodass für alle Wörter z ∈ Σ* mit |z| = n eine Zerlegung z = uvw existiert, wobei u,w ∈ Σ* und v ∈ Σ+ gelten. Dabei ist Σ* die Menge aller Wörter über dem Alphabet Σ, auch des leeren Wortes; Σ+ enthält nur nichtleere Wörter.
Für alle i ≥ 0 und alle Suffixe x ∈ Σ* muss dann gelten: zx ∈ L genau dann, wenn uv^i wx ∈ L. Das heißt: Durch das Pumpen von v ändert sich für beliebige Fortsetzungen x nicht, ob das entstehende Wort zur Sprache gehört.
Kontextfreie Sprachen
Für jede kontextfreie Sprache L gibt es eine natürliche Zahl n, sodass jedes Wort z in L mit Mindestlänge n eine Zerlegung z = uvwxy besitzt. Diese Zerlegung muss drei Bedingungen erfüllen:
- Die Wörter v, w und x haben zusammen höchstens die Länge n, also |vwx| ≤ n.
- Mindestens eines der Wörter v und x ist nicht leer, also |vx| ≥ 1.
- Für jede natürliche Zahl mit 0, also i ∈ ℕ₀, liegt uv^i w x^i y in L. Beispiele sind uwy, uvwxy, uvvwxxy usw.
Die Idee ist ähnlich wie bei regulären Sprachen, aber sie beruht auf Ableitungsbäumen kontextfreier Grammatiken. In einer kontextfreien Grammatik in Chomsky-Normalform mit N Variablen betrachtet man ein Wort x mit |x| ≥ 2^|N| = n. Der Ableitungsbaum ist ein Binärbaum. Auf einem langen Pfad von der Wurzel zu einem Blatt müssen zwei Knoten dieselbe Variable darstellen. Der Weg zwischen diesen beiden gleichen Variablen kann wiederholt werden. Dadurch entstehen Wörter der Form uv^i w x^i y, die weiterhin in der Sprache liegen.
Als Beispiel betrachtet der Artikel L = {a^m b^m c^m | m ≥ 1}. Angenommen, diese Sprache sei kontextfrei, und n sei die Pumping-Konstante. Für z = a^n b^n c^n müsste es eine Zerlegung z = uvwxy mit |vx| ≥ 1, |vwx| ≤ n und uv^i w x^i y ∈ L für alle i ≥ 0 geben. Da |vwx| ≤ n gilt, enthält vwx höchstens zwei verschiedene Buchstaben. Beim Pumpen mit i = 2 können daher nicht alle drei Buchstaben a, b und c in gleicher Anzahl bleiben. Das entstehende Wort liegt nicht in L. Also ist L nicht kontextfrei.
Auch hier gilt die Umkehrung nicht allgemein. Der Artikel nennt nicht-kontextfreie Sprachen, die das Pumping-Lemma trotzdem erfüllen, etwa L₁ = {$^+(a^n b^n)^n | n ∈ ℕ} und L₂ = {a^k b^l c^m d^n | k,l,m,n ∈ ℕ : k = 0 oder l = m = n}. Eine Verallgemeinerung des Pumping-Lemmas für kontextfreie Sprachen ist Ogdens Lemma.
