Lektion 2.3

Grenzen endlicher Automaten: das Pumping-Lemma

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • mit dem Schubfachprinzip begründen, warum ein langer Lauf eines DEA einen Zustand wiederholt,

  • das Pumping-Lemma für reguläre Sprachen mit seiner Quantorenstruktur genau aufschreiben und beweisen,

  • Nicht-Regularitätsbeweise als Spiel gegen einen Gegner führen, etwa für anbna^n b^n, Palindrome und am2a^{m^2},

  • typische Fehler in solchen Beweisen erkennen und Abschlusseigenschaften als zweiten Weg nutzen.

Vorausgesetzt: Deterministische endliche Automaten (DEA), Nichtdeterministische Automaten und die Potenzmengenkonstruktion, Reguläre Ausdrücke und der Satz von Kleene

Kann ein endlicher Automat prüfen, ob in einem Wort gleich viele Zeichen a wie b stehen, die a alle vorn? Probierst du es aus, merkst du schnell das Problem: Nach dem Lesen der a muss der Automat wissen, wie viele es waren, und mit endlich vielen Zuständen kann er nur endlich viele Anzahlen auseinanderhalten.

Das ist eine gute Ahnung, aber noch kein Beweis. Dass dir kein Automat einfällt, heißt nicht, dass es keinen gibt. In dieser Lektion machst du aus der Ahnung ein Werkzeug: Du zeigst, dass jede reguläre Sprache eine bestimmte Wiederholungseigenschaft hat, das Pumping-Lemma. Fehlt einer Sprache diese Eigenschaft, kann sie nicht regulär sein. Gemeint ist die Sprache L={anbn:n≥0}L = \{a^n b^n : n \ge 0\}; dabei steht ana^n für nn aufeinanderfolgende a, und a0a^0 ist das leere Wort ε\varepsilon.

Vermute zuerst

Ein DEA hat 33 Zustände und liest ein Wort der Länge 44. Der Lauf ist die Folge der Zustände, die er dabei durchläuft, den Startzustand mitgezählt. Was kannst du sicher sagen, ohne den Automaten zu kennen?

Beispiel

Eine Schleife im Lauf

Der Automat „Binärzahl modulo 3“ hat die Zustände q0,q1,q2q_0, q_1, q_2; der Zustand qrq_r bedeutet „die bisher gelesene Binärzahl hat beim Teilen durch 33 den Rest rr“. Endzustand ist q0q_0. Für das Wort 10011001 (dezimal 99) ist der Lauf

q0→1q1→0q2→0q1→1q0q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_1 \xrightarrow{1} q_0.

Der Zustand q1q_1 kommt nach dem ersten und nach dem dritten Zeichen vor. Das Stück 0000 dazwischen führt also von q1q_1 zurück nach q1q_1, es ist eine Schleife. Wir zerlegen das Wort in u=1u = 1 (bis zur Schleife), v=00v = 00 (die Schleife) und w=1w = 1 (der Rest).

uv0w=11  (=3),uv1w=1001  (=9),uv2w=100001  (=33)u v^0 w = 11 \;(=3), \qquad u v^1 w = 1001 \;(=9), \qquad u v^2 w = 100001 \;(=33)

Dabei ist viv^i das Wort vv, ii-mal hintereinander geschrieben, und v0=εv^0 = \varepsilon. Weil vv von q1q_1 nach q1q_1 führt, ist es dem Automaten gleich, wie oft er die Schleife durchläuft: Nach uviu v^i steht er immer in q1q_1, und ww bringt ihn dann nach q0q_0. Alle Wörter uviwu v^i w werden angenommen, und tatsächlich sind 33, 99 und 3333 durch 33 teilbar.

Binärzahl modulo 3: ein Lauf mit Schleife
010101q0q1q2

Der Pfeil von links zeigt den Start. Ein Doppelkreis ist ein Zustand, in dem ein Wort angenommen wird. Der hervorgehobene Zustand ist gerade aktiv.

  1. 0
  2. 0
  3. 1
Im Simulator öffnen

Start. Der Automat steht in q0. Drücke „Schritt“, um das erste Zeichen zu lesen.

Drei Zustände, vier Zeichen: Der Lauf muss einen Zustand zweimal besuchen.

Probier es aus

Satz

Pumping-Lemma für reguläre Sprachen

Sei LL eine reguläre Sprache. Dann gibt es eine Zahl n≥1n \ge 1, sodass sich jedes Wort z∈Lz \in L mit Länge ∣z∣≥n|z| \ge n so in drei Teile z=uvwz = uvw zerlegen lässt, dass gilt:

  • ∣uv∣≤n|uv| \le n (die Schleife beginnt und endet in den ersten nn Zeichen),
  • ∣v∣≥1|v| \ge 1 (die Schleife ist nicht leer),
  • uviw∈Lu v^i w \in L für alle i≥0i \ge 0 (man darf die Schleife beliebig oft durchlaufen oder weglassen).

Die Zahl nn heißt Pumping-Konstante. Als Formel, mit ∃\exists für „es gibt“ und ∀\forall für „für alle“:

∃n≥1    ∀z∈L, ∣z∣≥n    ∃u,v,w mit z=uvw,  ∣uv∣≤n,  ∣v∣≥1    ∀i≥0:  uviw∈L\exists n \ge 1 \;\; \forall z \in L,\, |z| \ge n \;\; \exists u,v,w \text{ mit } z = uvw,\; |uv| \le n,\; |v| \ge 1 \;\; \forall i \ge 0 : \; u v^i w \in L
Definition

Das Pumping-Spiel

Um zu zeigen, dass LL nicht regulär ist, verneinst du die Aussage des Lemmas. Beim Verneinen wird jedes ∃\exists zu ∀\forall und umgekehrt, die Reihenfolge bleibt:

Für jedes n≥1n \ge 1 gibt es ein z∈Lz \in L mit ∣z∣≥n|z| \ge n, sodass für jede Zerlegung z=uvwz = uvw mit ∣uv∣≤n|uv| \le n und ∣v∣≥1|v| \ge 1 ein i≥0i \ge 0 existiert mit uviw∉Lu v^i w \notin L.

Das liest man am besten als Spiel. Die „für alle“-Stellen wählt ein Gegner, der dir schaden will; die „es gibt“-Stellen wählst du. Du gewinnst, wenn du jede mögliche Wahl des Gegners beantworten kannst.

ZugWerWas wird gewählt
1Gegnereine Zahl n≥1n \ge 1
2duein Wort z∈Lz \in L mit ∣z∣≥n|z| \ge n, abhängig von nn
3Gegnereine Zerlegung z=uvwz = uvw mit ∣uv∣≤n|uv| \le n, ∣v∣≥1|v| \ge 1
4duein i≥0i \ge 0 mit uviw∉Lu v^i w \notin L

Hast du eine Gewinnstrategie, erfüllt LL das Pumping-Lemma nicht und ist daher nicht regulär.

Kurz geprüft

Im Pumping-Spiel für eine Sprache LL: Welche Wahl triffst du?

Schritt für Schritt

L={anbn:n≥0}L = \{a^n b^n : n \ge 0\} ist nicht regulär

Wir spielen das Spiel und zeigen, dass du jede Wahl des Gegners beantworten kannst.

  1. Der Gegner wählt ein beliebiges n≥1n \ge 1.

Schritt 1 von 4
Beispiel

Palindrome sind nicht regulär

Ein Palindrom ist ein Wort, das rückwärts gelesen gleich bleibt; mit xRx^R für das umgedrehte Wort xx ist das x=xRx = x^R. Sei P={x∈{a,b}∗:x=xR}P = \{x \in \{a, b\}^* : x = x^R\}.

Zum gegebenen nn wählst du z=anbanz = a^n b a^n. Es ist ein Palindrom mit ∣z∣=2n+1≥n|z| = 2n + 1 \ge n. Für jede Zerlegung mit ∣uv∣≤n|uv| \le n liegen uu und vv im vorderen a-Block, also v=akv = a^k mit k≥1k \ge 1. Mit i=2i = 2 entsteht

uv2w=an+k b an,(uv2w)R=an b an+ku v^2 w = a^{n+k}\, b\, a^n, \qquad (u v^2 w)^R = a^n\, b\, a^{n+k}

Die beiden Wörter sind verschieden, weil das b an verschiedenen Stellen steht (n+k≠nn + k \ne n). Also ist uv2w∉Pu v^2 w \notin P, und PP ist nicht regulär. Beachte die Wahl von zz: Das einzelne b in der Mitte sorgt dafür, dass der Gegner nur im vorderen Block zerlegen kann. Mit z=a2nz = a^{2n}, ebenfalls ein Palindrom, verlierst du dagegen: Jedes aja^j ist ein Palindrom, egal wie gepumpt wird.

Schritt für Schritt

Quadratzahlen: Q={am2:m≥0}Q = \{a^{m^2} : m \ge 0\}

Hier hilft keine Reihenfolge der Zeichen, denn es gibt nur eines. Das Argument läuft über die Länge.

  1. Zum gegebenen nn wählst du z=an2z = a^{n^2}; es ist ∣z∣=n2≥n|z| = n^2 \ge n.

Schritt 1 von 4
Häufige Fehler

Selbst ein nn wählen oder nur eine Zerlegung prüfen

Zwei Fehlschlüsse kommen in Klausuren immer wieder vor:

  • „Sei n=3n = 3. Dann ist z=aaabbbz = aaabbb …“ Das zeigt nur, dass die Konstante 33 nicht passt. Der Automat könnte 100100 Zustände haben.
  • „Zerlege z=anbnz = a^n b^n als u=εu = \varepsilon, v=anbnv = a^n b^n, w=εw = \varepsilon; dann ist v2=anbnanbn∉Lv^2 = a^n b^n a^n b^n \notin L.“ Erstens verletzt diese Zerlegung ∣uv∣≤n|uv| \le n, zweitens ist das nur eine von vielen. Das Lemma behauptet die Existenz einer guten Zerlegung, also musst du alle zulässigen widerlegen.
Richtig ist

Das nn bleibt eine Variable, über die du nichts weißt außer n≥1n \ge 1. Das Wort zz hängt von nn ab. Die Zerlegung beschreibst du allgemein (v=akv = a^k mit 1≤k≤n1 \le k \le n), sodass dein Argument jede Wahl des Gegners abdeckt.

Satz

Das Pumping-Lemma ist nur notwendig

Es gibt Sprachen, die das Pumping-Lemma erfüllen und trotzdem nicht regulär sind. Ein Beispiel über {a,b,c}\{a, b, c\}:

L={aibjck:i≥1, j=k}∪{bjck:j,k≥0}L = \{a^i b^j c^k : i \ge 1,\ j = k\} \cup \{b^j c^k : j, k \ge 0\}.

Das Pumping-Lemma kann also nur Nicht-Regularität zeigen, nie Regularität.

Beispiel

Abschlusseigenschaften als zweiter Weg

Oft ist es kürzer, eine Sprache auf eine schon bekannte nicht reguläre Sprache zurückzuführen. Sei E={x∈{a,b}∗:x entha¨lt gleich viele a wie b}E = \{x \in \{a, b\}^* : x \text{ enthält gleich viele a wie b}\}.

Angenommen, EE wäre regulär. Die Sprache a∗b∗a^* b^* ist regulär (sie hat einen regulären Ausdruck), und reguläre Sprachen sind unter Schnitt abgeschlossen. Dann wäre auch

E∩a∗b∗={anbn:n≥0}E \cap a^* b^* = \{a^n b^n : n \ge 0\}

regulär, im Widerspruch zum Beweis oben. Also ist EE nicht regulär. Genauso kannst du mit dem Komplement arbeiten: Ist LL regulär, so auch L‾=Σ∗∖L\overline{L} = \Sigma^* \setminus L. Und auch die Sprache LL aus dem letzten Satz ließ sich nur so als nicht regulär entlarven, weil das Pumping-Lemma bei ihr versagt.

Kurz geprüft

Die Sprache LL erfüllt das Pumping-Lemma mit der Konstante n=5n = 5. Was folgt daraus?

Zusammenfassung

  • Schubfachprinzip: Ein Lauf eines DEA mit nn Zuständen auf mindestens nn Zeichen wiederholt einen Zustand; das Stück dazwischen ist eine Schleife.

  • Pumping-Lemma: Ist LL regulär, gibt es n≥1n \ge 1, sodass jedes z∈Lz \in L mit ∣z∣≥n|z| \ge n eine Zerlegung z=uvwz = uvw mit ∣uv∣≤n|uv| \le n, ∣v∣≥1|v| \ge 1 und uviw∈Lu v^i w \in L für alle i≥0i \ge 0 hat.

  • Nicht-Regularität als Spiel: Der Gegner wählt nn und die Zerlegung, du wählst zz (abhängig von nn) und ii.

  • Mit diesem Spiel sind {anbn}\{a^n b^n\}, die Palindrome und {am2}\{a^{m^2}\} nicht regulär.

  • Typische Fehler: ein festes nn einsetzen, nur eine Zerlegung prüfen, zz ungeschickt wählen.

  • Das Lemma ist nur notwendig: Es gibt nicht reguläre Sprachen, die es erfüllen.

  • Abschlusseigenschaften (Schnitt mit einer regulären Sprache, Komplement) führen oft schneller zum Ziel.

Übungen

Aufgabe 1Multiple Choice

Welche Formel ist die Verneinung der Pumping-Eigenschaft, also das, was du für eine nicht reguläre Sprache zeigst? (Die Bedingungen an zz und die Zerlegung sind jeweils mitgemeint.)

Aufgabe 2Numerisch

Der Automat „Binärzahl modulo 3“ aus der Lektion liest z=10010z = 10010. Nimm wie im Beweis die erste Stelle, an der sich ein Zustand im Lauf wiederholt, und zerlege z=uvwz = uvw. Welchen Dezimalwert hat die Binärzahl uv0wu v^0 w?

Aufgabe 3Multiple Choice

Im Spiel für {anbn}\{a^n b^n\} hat der Gegner n=4n = 4 gewählt, und du hast z=a4b4z = a^4 b^4 gewählt. Welche Zerlegung darf der Gegner nicht wählen?

Aufgabe 4Freitext

Zeige mit dem Pumping-Lemma, dass L={aibj:i>j≥0}L = \{a^i b^j : i > j \ge 0\} nicht regulär ist.

Aufgabe 5Freitext

Zeige ohne Pumping-Lemma, nur mit Abschlusseigenschaften und dem Ergebnis für {anbn}\{a^n b^n\}, dass U={aibj:i≠j}U = \{a^i b^j : i \ne j\} nicht regulär ist.

Aufgabe 6Freitext

Zeige, dass {ap:p ist eine Primzahl}\{a^p : p \text{ ist eine Primzahl}\} nicht regulär ist.