Theoretische Informatik

Satz:  (Pumping-Lemma)

Sei A ein Alphabet und L ⊆ A* eine reguläre Sprache. Dann lassen sich alle Wörter x ∈ L ab einer gewissen Länge |x| ≥ p (der Pumping-Länge) zerlegen in

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

mit

0  <  |v|  ≤  |uv|  ≤  p ,

sodass gilt

uv^kw ∈ L   für alle k ∈ ℕ₀.

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 = x₀ ... x_m-1 der Länge m ≥ p erkennt, so gibt es einen mit x markierten Pfad vom Startzustand q = s₀ zu einem Endzustand s_m ∈ 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 j ≤ p geben, derart dass s₀, ..., s_j-1 verschieden sind und s_j = s_i für ein i ∈ {0, ..., j-1}. Der Automat gelangt also mit x₀ ... x_i-1 ausgehend von Startzustand s₀ in den Zustand s_i, von dort mit x_i ... x_j-1 in den Zustand s_j = s_i, und von dort mit x_j ... x_m-1 in den Zustand s_m. Der Pfad von s₀ nach s_m im Zustands­graphen enthält also einen Zyklus, der mit x_i ... x_j-1 markiert ist. Dieser Zyklus kann mehrfach oder auch gar nicht durchlaufen werden (Bild 1).

Somit lässt sich x  =  x₀ ... x_m-1 darstellen als

x  =  uvw  mit

u  =  x₀ ... x_i-1

v  =  x_i ... x_j-1

w  =  x_j ... x_m-1

und es gilt

0  <  |v|,   da  i < j,

|uv| ≤ p,   da  j ≤ p

sowie

uv^kw ∈ L   für alle k ∈ ℕ₀.

Satz:  Die Sprache L = { aⁿbⁿ  |  n ∈ ℕ } ist nicht regulär.

Beweis:  Angenommen, L ist regulär. Dann gilt das Pumping-Lemma. Sei nun p die Pumping-Länge und sei x = a^pb^p. Dann gilt |x| ≥ p und x lässt sich somit darstellen als x  = uvw mit

0  <  |v|  ≤  |uv|  ≤  p

Da |uv| ≤ p, 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 uv²w  = a^p+rb^p  ∈  L, im Widerspruch zur Definition von L. Also ist die Annahme falsch, L ist also nicht regulär.

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 ∈ {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.

Hinweis: Beginnen Sie Ihren Beweis so: "Angenommen, die Sprache L ist regulär. Dann gilt das Pumping-Lemma. Sei p die Pumping-Länge und sei x =  ... "

Aufgabe 2:  

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

L  =  { ww^R  |  w ∈ {a, b}*,  w^R ist das Spiegelbild von w }

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

Hinweis: Beginnen Sie Ihren Beweis so: "Angenommen, die Sprache L ist regulär. Dann gilt das Pumping-Lemma. Sei p die Pumping-Länge und sei x =  ... "