Theoretische Informatik

Pumping Lemma

Dieser Artikel behandelt das Pumping Lemma für reguläre und kontextfreie Sprachen. Zuerst wird allgemein erläutert, worum es sich hierbei überhaupt handelt. Danach wird das Pumping Lemma einfach erklärt, mittels verschiedener Pumping Lemma Beispiele – jeweils einmal für die reguläre und auch für die kontextfreie Sprache. Dabei gibt es für beide Fälle den Pumping Lemma Beweis.

Keine Lust schon wieder so viel Text zu lesen? Kein Problem! Unser Video bringt alles was du bezüglich dem Pumping Lemma (Reguläre Sprachen) wissen musst schnell und einfach auf den Punkt.

Inhaltsübersicht

Pumping Lemma Definition

Das Pumping Lemma, auch Schleifensatz genannt, stellt in der theoretischen Informatik eine Bedingung für die Eigenschaft einer formalen Sprache dar. Mit ihm kann gezeigt werden, ob es sich bei einem Ausdruck um eine reguläre oder kontextfreie Sprache handelt.

Pumping Lemma
direkt ins Video springen
Pumping Lemma

Pumping Lemma einfach erklärt!

Das Prinzip des Pumping Lemma einfach erklärt:

„Beweis durch Widerspruch“

Das bedeutet nichts anderes, als zu zeigen, dass Sprachen, die nicht regulär oder nicht kontextfrei sind, das Pumping Lemma verletzen. Dabei muss aber beachtet werden, dass das nicht automatisch heißt, dass sobald ein Pumping Lemma erfüllt wird, es sich auch wirklich um eine reguläre oder kontextfreie Sprache handelt. In unseren Videos zu reguläre Sprachen  oder kontextfreien Sprachen erfährst du, wie man Regularität nachweist.

Für den Widerspruchsnachweis muss aber zwischen dem Pumping Lemma für reguläre Sprachen und kontextfreie Sprachen unterschieden werden. Im Allgemeinen können  aber durch das Lemma Wörter beliebig vergrößert oder verkleinert, oder in anderen Worten auch auf- bzw. abgepumpt werden. Ist dies nicht möglich, gilt die Bedingung als verletzt.

Pumping Lemma Reguläre Sprachen

Reguläre Sprachen lassen sich durch endliche Automaten erzeugen. Beispielsweise der folgende Automat:

Pumping Lemma Reguläre Sprache
direkt ins Video springen
Pumping Lemma Reguläre Sprache

Der Automat beschreibt eine Sprache, die aus den Wörtern a(bcd)^{i}b besteht. Im hinteren Teil des Automaten ist also direkt eine Schleife zu erkennen, besteht aus b, c und d. Mit dem Pumping Lemma für reguläre Sprachen lässt sich die Schleife also beliebig oft durchlaufen.

Formale Definition

Formal lässt sich das Lemma wie folgt definieren:

Gegeben ist dabei die Sprache L. Wörter z der Sprache, die mindesten eine Länge n aufweisen, lassen sich so in die Teile u v und w zerlegen, wodurch drei Eigenschaften gelten:

  • Die beiden Teilwörter u und v haben zusammen höchstens die Länge n
  • Das Wort v ist nicht leer
  • Für jede Zahl i ist das Wort uv^{i}w in der Sprache.

N wird auch Pumping-Zahl genannt. Sie muss mindestens so lang sein, dass das Wort z den Anfangsteil u, den Endteil w und den Schleifenteil v des Automaten umfasst.

Das Schleifenteil v pumpt das Wort auf oder ab. Entsprechend darf der Schleifenteil des Wortes natürlich nicht die leere Menge sein, ansonsten würde die Möglichkeit bestehen, dass jedes beliebige Wort aufgepumpt werden könnte. Die dritte Bedingung sagt nun, dass man ein Wort aus L mit dem Schleifenteil beliebig groß aufpumpen können muss.

Innerhalb des oben genannten Automaten wäre:

u=a
v=〖(bcd)〗^{i}
w=b

Dadurch können nun alle Wörter der Sprache erzeugt werden, z.B.:

  • i = 0 ist ab
  • i = 3 ist a(bcd)(bcd)(bcd)b

Pumping Lemma Beispiel

Für unser Pumping Lemma Beispiel ist die folgende Sprache gegeben:

L=(a^{l} b^{m} \mid l<m,l>0)

Die Wörter der Sprache L bestehen aus einer beliebigen, positiven Anzahl a’s gefolgt von noch mehr b’s. Formal geht man zunächst davon aus, dass es sich hierbei um eine reguläre Sprache handelt. Im nächsten Schritt soll dann ein Wort x aus der Sprache ausgewählt werden. In diesem Fall kann das beispielsweise x= a^{n} b^{n+1} \in L sein.

Das Wort entspricht der Sprache, da mehr b’s als a’s enthalten sind. Die Wortlänge beträgt dabei {2n + 1} und ist damit länger als die Pumping Zahl.

\vert x \vert = 2n+1 \geq n

Pumping Lemma Beweis

Laut Lemma ist es nun möglich, das Wort beliebig auf- oder abzupumpen. Die neu erzeugten Wörter müssen dabei immer in der Sprache liegen. Der Pump-Faktor wird dabei mit i bezeichnet.

uv^{i} w=a^{n-k} (a^{k})^{i} b^{n+1}

Mit dem v-Teil können beliebig viele a’serzeugt werden, da das Ganze unabhängig von n verläuft. Dadurch können immer mehr a’s als b’s erzeugt werden, wodurch letztendlich das Lemma widerlegt wird.

Für den Pumping Lemma Beweis werden nun die Exponenten zusammengefasst:

a^{n+k(-1+i)} b^{n+1}

Im nächsten Schritt wird nun ein i gewählt, mit dem die Bedingung des Lemma verletzt wird, bspw. i = 3:

a^{n+k(-1+3)} b^{n+1}= a^{n+2k} b^{n+1}

Vergleiche Exponenten: n+2k>n+1:

Da k größer als Null sein muss, erhält man für i = 3 mehr a’s im Wort als b’s. Das Pumping Lemma ist verletzt und die Sprache gilt nun offiziell als nicht regulär.

Allgemein gilt: Alle Sprachen, die in irgendeiner Weise ein Mitzählen von Bestandteilen eines Wortes erfordern, gelten als nicht regulär!

Pumping Lemma Kontextfreie Sprache

Durch das Pumping Lemma für kontextfreie Sprache, kann nur gezeigt werden, dass eine Sprache nicht kontextfrei ist. Um zu zeigen, dass es sich um eine kontextfreie Sprache handelt, muss eine kontextfreie Grammatik angegeben werden, die diese erzeugt.

Gegeben sei dabei wieder eine Sprache L, die eine natürlichen Zahl n besitzt. Dabei lassen sich alle Wörter z in L, die mindestens eine Länge von n aufweisen mit z = uvwxy darstellen. Dabei gelten die folgenden drei Bedingungen:

  • Die drei Teilwörter v, w und x haben zusammen höchstens die Länge n
  • Das Wort v oder x ist nicht leer
  • Für jede Zahl i ist das Wort uv^{i}wx^{i}y in der Sprache.

Pumping Lemma Aufgabe

Als weiteres Beispiel, folgt nun eine Aufgabe, in der nachgewiesen werden soll, dass es sich bei der Sprache L nicht um eine kontextfreie Sprache handelt. Gegeben sei dafür:

L=\{x^{n} y^{n} z^{n} \mid n \geq 1\}

Zu beginn wird angenommen, dass die Sprache kontextfrei ist. Das Wort \omega ist dabei mindestens so groß wie die Pumping-Länge p, weshalb gilt:

\omega \geq p

Im nächsten Schritt wird versucht die Wortteile v und x i-mal zu wiederholen.

uv^{i}wx^{i}y

Ergibt sich hierbei ein Wort, das nicht in der Sprache L liegt, gilt die Sprache als nicht kontextfrei.

Pumping Lemma Beweis

Für den Beweis bildet man ein Wort \omega  mit der Pumping-Zahl p, bspw.:

\omega = x^{p}y^{p}z^{p}

v, w und x dürfen höchstens p-Zeichen lang sein. Für p = 2 ergibt sich das Wort

\omega = xxyyzz

Versucht man dann das Wort so zu zerteilen, dass im Teilwort vwx alle drei Zeichen auftreten, überschreitet man das p von 2. Daraus folgt, dass in vwx nur maximal zwei verschiedene Buchstaben vorkommen können.

Innerhalb von uv^{i}wx^{i}y lassen sich nie alle drei Buchstaben vervielfachen, da im Teilwort vwx nie alle drei Buchstaben enthalten sein können. Dadurch wird im Wort beispielsweise nur die Buchstaben x und y vervielfacht, aber das z nicht. Dadurch befindet sich das Wort xxyyz nicht mehr in der Sprache L und ist somit nicht kontextfrei.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.