Pumping-Lemma

Satz über eine Eigenschaft von formalen Sprachen in der theoretischen Informatik

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 SprachenBearbeiten

Pumping-Lemma für reguläre SprachenBearbeiten

Für jede reguläre Sprache   gibt es eine natürliche Zahl  , sodass gilt: Jedes Wort   in   mit Mindestlänge   hat eine Zerlegung   mit den folgenden drei Eigenschaften:

  1. Die beiden Wörter   und   haben zusammen höchstens die Länge  .
  2. Das Wort   ist nicht leer.
  3. Für jede natürliche Zahl (mit 0)   ist das Wort   in der Sprache  , d. h. die Wörter  ,  ,  ,   usw. sind alle in der Sprache  .

Das kleinste  , das diese Eigenschaften erfüllt, wird Pumping-Zahl der Sprache   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   die Menge aller regulärer Sprachen.

 

BeweisBearbeiten

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   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   eine reguläre Sprache. Ist   endlich, dann gibt es ein Wort mit maximaler Länge  . Sei  , so ist für alle   die Prämisse   falsch und die Implikation damit wahr.

Ist   unendlich, dann sei   ein deterministischer endlicher Automat, der   akzeptiert. Da   regulär ist, existiert ein solcher Automat   immer. Sei   die Anzahl der Zustände dieses Automaten, und sei   ein beliebiges Wort aus   mit mindestens   Zeichen. Bezeichne nun mit   die Zustandsfolge, die   beim Lesen von   beginnend mit dem Startzustand   durchläuft. Da   in   ist, muss   von   akzeptiert werden, d. h.   muss ein akzeptierender Zustand sein. Da der Automat   gerade   Zustände hat, muss spätestens nach dem Lesen von   Zeichen eine Zustandswiederholung eintreten. Das heißt, es existieren   mit   und  . Der Automat   durchläuft beim Lesen von   also einen Zyklus.

Sei   der Teil von  , der beim Durchlaufen des Zyklus   gelesen wird. Ferner sei   der Teil von  , der beim Durchlaufen der davor liegenden Zustandsfolge   gelesen wird, und   sei der Teil von  , der beim Durchlaufen der dahinter liegenden Zustandsfolge   gelesen wird. Mit dieser Wahl gilt  .

Mit dieser Wahl von  ,   und   gelten die Aussagen aus dem Pumping-Lemma:

  1. Die Länge von   ist   und somit nicht größer als  .
  2. Das Wort   ist nicht leer, da   gilt, so dass beim Durchlauf des Zyklus mindestens ein Zeichen gelesen wird.
  3. Für beliebiges   durchläuft der Automat beim Lesen des Worts   zunächst die Zustandsfolge  , dann  -mal den Zyklus   und schließlich die Zustandsfolge  . Am Ende befindet sich der Automat im akzeptierenden Zustand  . Somit gilt   für alle  .

BeispielBearbeiten

Ist die Sprache   regulär?

Angenommen,   sei eine reguläre Sprache. Dann gibt es gemäß Pumping-Lemma eine Zahl  , so dass sich alle Wörter   mit   wie beschrieben zerlegen lassen.

Insbesondere gibt es eine Zerlegung   mit den beschriebenen Eigenschaften für das Wort  . Da   ein Präfix dieses Wortes ist und gemäß Eigenschaft 1 höchstens Länge   hat, besteht   und damit   ausschließlich aus Buchstaben  . Gemäß Eigenschaft 3 (für  ) muss auch das Wort   in   liegen. Da aber   (Eigenschaft 2), enthält dieses Wort mehr   als  , liegt also nicht in  .

Also führt die Annahme,   sei eine reguläre Sprache, zum Widerspruch und ist damit falsch.

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

Die Sprache   ist nicht regulär. Allerdings erfüllt   die Eigenschaften des Pumping-Lemmas, denn jedes Wort   lässt sich so zerlegen  , dass auch für alle    . Dazu kann   einfach als erster Buchstabe gewählt werden. Dieser ist entweder ein  , die Anzahl von führenden  s ist beliebig. Oder er ist ein   oder  , ohne führende  s ist aber die Anzahl von führenden  s oder  s beliebig.

Jaffes Pumping-LemmaBearbeiten

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   ist regulär genau dann, wenn eine Konstante   existiert, so dass es für alle  ,   eine Zerteilung   mit   gibt, so dass für alle   und Suffixe   gilt:

 .

Kontextfreie SprachenBearbeiten

Pumping-Lemma für kontextfreie SprachenBearbeiten

Für jede kontextfreie Sprache   gibt es eine natürliche Zahl  , sodass gilt: Jedes Wort   in   mit Mindestlänge   hat eine Zerlegung   mit den folgenden drei Eigenschaften:

  1. Die Wörter  ,   und   haben zusammen höchstens die Länge  , d. h.  .
  2. Eines der Wörter  ,   ist nicht leer. Also  .
  3. Für jede natürliche Zahl (mit 0)   ist das Wort   in der Sprache  , d. h. die Wörter  ,  ,   usw. liegen alle in  .

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.

BeweisBearbeiten

Gegeben sei eine kontextfreie Grammatik G in Chomsky-Normalform mit   Variablen, für die gilt, dass sie gerade die gewünschte Sprache beschreibt. Sei nun ein Wort   aus dieser Sprache gegeben, für das gilt:  .

 
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   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  . Es gibt also einen Pfad   in T von der Wurzel zu einem Blatt, für den gilt, dass er Länge   hat. Es existieren also zwei Knoten   auf diesem Pfad mit  , welche die gleichen Variablen von G   repräsentieren.

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

BeispielBearbeiten

 
Das Wort   enthält höchstens zwei verschiedene Buchstaben.

Ist die Sprache   kontextfrei?

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

Wir betrachten das Wort  . Es muss dann eine Zerlegung   geben, so dass  ,  ,   für alle   ist. Da  , enthält das Wort   höchstens zwei verschiedene Buchstaben. Deshalb, und da   gilt, enthält   nicht von allen drei Buchstaben gleich viele, ist also nicht in   enthalten. Das ist ein Widerspruch; die Annahme,   sei kontextfrei, ist also falsch.

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

Die Sprachen   und   sind nicht kontextfrei. Allerdings erfüllen   und   die Eigenschaften des Pumping-Lemmas: Enthält ein Wort   nicht den Buchstaben  , so gilt dies auch für alle Wörter  . Ist der Buchstabe   hingegen enthalten, gibt es eine Zerlegung mit   (  bezeichne das leere Wort),   und einem Suffix  , sodass abermals alle Wörter   in   enthalten sind. Für  lässt sich   und   wählen, und damit ist   in   enthalten.

EinzelnachweiseBearbeiten

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