Pumping Lemma

Das Pumping Lemma findet man auch unter der Bezeichnung Pumplemma, uvw-Theorem oder Schleifensatz wieder. Es ist eine Eigenschaft bestimmter Klassen formaler Sprachen. Mit dem Pumping Lemma lässt sich so nachweisen, ob eine Sprache nicht regulär, bzw. nicht kontextfrei ist. Wobei es hierfür jeweils zwei unterschiedliche Pumping Lemmas gibt. Der Begriff Pumping Lemma leitet sich aus der Beweisführung ab. Hierbei wird nämlich ein bestimmter Teil eines Wortes aufgepumpt (pump) und geschaut ob das so neu entstandene Wort ebenfalls in der Sprache ist oder nicht.

Unterschieden wird das Pumping Lemma in das Pumping-Lemma für reguläre Sprachen und jenem für kontextfreie Sprachen.

Pumping Lemma für reguläre Sprachen

Das Pumping Lemma dient als Nachweis, dass eine bestimmte Sprache nicht regulär ist. Achtung: Der Umkehrschluss gilt aber nicht! Selbst wenn die Wörter der Sprache alle Eigenschaften des Pumping Lemmas erfüllen, bedeutet dies nicht, dass die Sprache auch regulär ist.

Beim Pumping Lemma für reguläre Sprachen zerlegt man ein reguläres Wort einer gegebenen Sprache in die drei Teile x,y,z (man kann hier auch andere Buchstaben verwenden, oft auch u,v,w). Darauf setzt man dann folgende Definition an:

Sei L eine reguläre Sprache. Dann gibt es eine natürliche Zahl n ∈ Natürliche Zahl bei Pumping Lemma, so dass sich alle Wörter w ∈ L mit |w| ≥ n in w = xyz zerlegen lassen, wobei folgendes dabei gilt:
  1. |y| ≥ 1
  2. |xy| ≤ n
  3. ∀ i ≥ 0: xyiz ∈ L
Also noch einmal in Worte gefasst. Man nimmt erst einmal grundsätzlich an, dass die gegebene zu untersuchende Sprache regulär sei. Zu dieser Sprache gibt es dann eine natürliche Zahl n, wobei die Länge alle Wörter der Sprache größer dieses n sind. Nun nimmt man sich ein reguläres Wort aus dieser Sprache und zerlegt dieses in xyz. Der y-Teil darf dabei nicht leer sein (x und z aber schon). Weiter muss die Länge von x und y kleiner als das gewählte n sein.

Beispiele zum Pumping Lemma für reguläre Sprachen

Hier folgen nun einige Beispiele zum Pumping Lemma für reguläre Sprachen.

Beispiel 1

Das klassische Beispiel zum Pumping Lemma für reguläre Sprachen, das in so gut wie jedem Lehrbuch zu finden ist, darf natürlich auch an dieser Stelle nicht fehlen. Geben sei die Sprache L = {ambm | m ≥ 1}. Ist die Sprache regulär?

Angenommen die Sprache sei regulär, dann gibt es eine natürliche Zahl n ∈ Natürliche Zahl bei Pumping Lemma, so dass sich alle Wörter w ∈ L mit |w| ≥ n in w = xyz zerlegen lassen. Man nehme für w = xyz = anbn. Dies hat eine Länge von | n + n | = 2n und ist somit größer gleich n.

Nun geht man einfach die Punkte der oberen Definition durch.

Zu 1.)
y ist nicht leer

Zu 2.)
Da y nicht leer ist, die Länge von xy aber kleiner gleich n ist, kann y nur aus a's bestehen. Man setzt also |xy| = an. Daraus folgt das y=ak ist, wobei für k gilt: 1 ≤ k ≤ n. Der y-Teil kann also eine maximale Länge von n a's haben, besitzt aber mindestens ein a. Genauso könnte der y-Teil aber auch weniger als n a's haben, dann würde der x-Teil auch noch aus ein paar a's bestehen und wäre nicht leer. Also setzen wir für x gleich x=an-k. Wäre der y-Teil also n a's lang, dann wäre der x-Teil leer (n-n=0), was aber laut Definition kein Problem ist, lediglich der y-Teil des Worts darf ja nicht leer sein. So nun schaut man sich was noch übrig ist, das wäre bei dieser Sprache bn und das weisen wir unserem noch übrigen z-Teil zu. Zusammenfassend lässt sich also sagen, dass unsere xyz-Zerlegung die folgende ist: x=an-k, y=ak und z=bn.

xyz= an-kakbn = an-k+kbn=anbn und damit ist unser Wort eindeutig in unserer Sprache.

Zu 3.)
Da unser gewähltes Wort xyz= an-kakbn in unserer Sprache befindet, müsste sich auch xy2z in unserer Sprache befinden (oder auch eine andere Potenz von y). Dies ist aber nicht der Fall, denn xy2z= an-kak2bn=an-ka2kbn = an+kbn. Da k aber größer gleich eins ist, gibt es mehr a's als b's und damit liegt das Wort nicht in unserer Sprache.

Damit ist L nicht regulär!

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972