Theoretische Informatik

Pumping-Lemma für reguläre Sprachen

 aufwärts

Um zu zeigen, dass eine Sprache regulär ist, genügt es, einen regulären Ausdruck anzugeben, der sie erzeugt, oder einen endlichen Automaten anzugeben, der sie erkennt, oder eine rechts­lineare Grammatik anzugeben, die sie erzeugt.

Wie aber kann man zeigen, dass eine Sprache nicht regulär ist? Hierzu ist der folgende Satz ein wichtiges Hilfsmittel.

Pumping-Lemma

Satz:  (Pumping-Lemma)

Sei A ein Alphabet und L enthalten in A* eine reguläre Sprache. Dann lassen sich alle Wörter x Element L ab einer gewissen Länge |x|größer gleichp (der Pumping-Länge) darstellen als

x  =  uvw   mit   u, v, w Element A*

wobei

|v| > 0   und

|uv|kleiner gleichp ,

so dass gilt

uvkw Element L   für alle k Element natürliche Zahlen0.

Alle Wörter x ab einer gewissen Länge p (der Pumping-Länge) enthalten also ein Teilwort v, mit dem sich das Wort x "aufpumpen" lässt – daher die Bezeichnung Pumping-Lemma.

Beweis:  

Die Sprache L ist regulär, also gibt es einen deterministischen endlichen Automaten, der L erkennt. Sei p = |Z|, die Anzahl der Zustände dieses Automaten. Wenn der Automat ein Wort x = x0 ... xm-1 der Länge mgrößer gleichp erkennt, so gibt es einen mit x markierten Pfad vom Startzustand q = s0 zu einem Endzustand sm Element F im Zustands­graphen des Automaten. Dieser Pfad enthält m+1 > p Zustände. Diese können nicht alle verschieden sein, sondern es muss einen Index jkleiner gleichp geben, derart dass s0, ..., sj-1 verschieden sind und sj = si für ein i Element {0, ..., j-1}. Der Automat gelangt also mit x0 ... xi-1 ausgehend von Startzustand s0 in den Zustand si, von dort mit xi ... xj-1 in den Zustand sj = si, und von dort mit xj ... xm-1 in den Zustand sm. Der Pfad von s0 nach sm im Zustands­graphen enthält also einen Zyklus, der mit xi ... xj-1 markiert ist. Dieser Zyklus kann mehrfach oder auch gar nicht durchlaufen werden (Bild 1).

Somit lässt sich x  =  x0 ... xm-1 darstellen als

x  =  uvw  mit

u  =  x0 ... xi-1

v  =  xi ... xj-1

w  =  xj ... xm-1

und es gilt

|v| > 0,   da  i < j,

|uv|kleiner gleichp,   da  jkleiner gleichp

sowie

uvkw Element L   für alle k Element natürliche Zahlen0.

Bild 1: Zyklus im Zustandsgraphen
Bild 1: Zyklus im Zustandsgraphen

Anwendung

Satz:  Die Sprache L = { anbn  |  n Element natürliche Zahlen } ist nicht regulär.

Beweis:  Angenommen, L wäre regulär. Dann gilt das Pumping-Lemma. Sei nun p die Pumping-Länge und sei x = apbp. Dann gilt |x|größer gleichp und x lässt sich somit darstellen als x  = uvw mit

|v| > 0

|uvkleiner gleich p

Da |uv|kleiner gleichp, besteht uv nur aus a's, und damit besteht auch v nur aus a's. Sei r die Länge von v; es gilt r > 0. Dann ist nach dem Pumping-Lemma auch uv2w  = ap+rbp  Element  L, im Widerspruch zur Definition von L. Also ist die Annahme falsch, L ist also nicht regulär.

Die Anwendung des Pumping-Lemmas verläuft immer nach diesem Schema. Wir nehmen an, dass L regulär ist. Dann gilt das Pumping-Lemma, und es gibt somit eine Pumping-Länge p.

Jetzt müssen wir nur ein einziges Wort x Element L finden, das lang genug ist, d.h. mit |x|größer gleichp, und ein Anfangswort uv von x, das kurz genug ist, d.h. mit uvkleiner gleichp, und das so beschaffen ist, dass wir in uv einen beliebigen Teil v "aufpumpen" können, um Wörter zu erhalten, die nicht in L liegen. Damit erhalten wir einen Widerspruch zur Annahme, dass L regulär ist.

In obigem Beweis haben wir dafür gesorgt, dass uv nur aus a's besteht. Somit besteht auch das Teilwort v nur aus a's, ganz gleich, welchen Teil von uv es einnimmt. Wird nun v "aufgepumpt", so entstehen Wörter mit mehr a's als b's, also Wörter, die nicht in L liegen. Damit kann L nicht regulär sein.

Aufgaben

Aufgabe 1:  

Sei L die Sprache aller Wörter über dem Alphabet A = {a, b}, die aus gleich vielen a's und b's bestehen, d.h.

L  =  { w Element {a, b}*  |  |w|a = |w|b }

Die Notation |w|a bezeichnet die Anzahl der a's im Wort x.

Zeigen Sie durch Anwendung des Pumping-Lemmas: L ist nicht regulär.

Aufgabe 2:  

Sei L die Sprache der Palindrome1) gerader Länge über dem Alphabet A = {a, b}, d.h.

L  =  { wwR  |  w Element {a, b}*,  wR ist das Spiegelbild von w }

Zeigen Sie durch Anwendung des Pumping-Lemmas: L ist nicht regulär.

 

 


1)  Ein Palindrom ist ein Wort, das man vorwärts und rückwärts lesen kann, wie z.B. otto.

 

Weiter mit:  [Grammatik]  oder  up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2007   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik