Pumping-Lemma für reguläre Sprachen

Klausur-Relevanz: sehr hoch · Lesen UND Rechnen

Ein Widerspruchswerkzeug, um zu zeigen, dass eine Sprache nicht regulär sein kann — durch Ausnutzen der endlichen Zustandsmenge jedes DEA. Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben.

TL;DR

Jede reguläre Sprache $L$ besitzt eine Pumping-Zahl $n$: für jedes hinreichend lange Wort $w \in L$ gibt es eine Zerlegung $w = xyz$ mit $|xy| \leq n$, $|y| \geq 1$, so dass $xy^i z \in L$ für alle $i \geq 0$.

Anwendung: Kontraposition. Zeige, dass für ein geschickt gewähltes $w$ jede zulässige Zerlegung beim Pumpen ein Wort außerhalb von $L$ erzeugt.

Reihenfolge der Quantoren ist entscheidend: für alle Zerlegungen muss ein Widerspruch gezeigt werden, aber nur ein passendes $i$ reicht.

Das Lemma ist eine notwendige, aber nicht hinreichende Bedingung: ein bestandener Pumping-Test beweist keine Regularität.

Klassiker: $\{a^n b^n\}$, $\{ww\}$, $\{a^p : p \text{ prim}\}$ — alle nicht regulär.

Neu auf dieser Seite: vollständig durchgerechnete Klausur-Beweise inklusive Fallunterscheidungen und Pumping-Wahl im Abschnitt Rechenaufgaben mit Lösung.

1 · Definitionen & Formalismen

Pumping-Lemma (regulär)

Sei $L$ eine reguläre Sprache. Dann existiert eine natürliche Zahl $n \geq 1$ (die Pumping-Zahl), so dass für jedes $w \in L$ mit $|w| \geq n$ eine Zerlegung $w = xyz$ existiert mit:

$$|xy| \leq n \quad\wedge\quad |y| \geq 1 \quad\wedge\quad \forall\, i \geq 0:\; xy^i z \in L$$

Formal als geschlossene Aussage:

$$\exists\, n \geq 1\; \forall\, w \in L,\, |w| \geq n\; \exists\, x,y,z:\; w = xyz \,\wedge\, |xy| \leq n \,\wedge\, |y| \geq 1 \,\wedge\, \forall\, i \geq 0:\; xy^i z \in L$$

Kontraposition (Beweisrichtung)

Ist die Aussage des Lemmas für $L$ verletzt, so ist $L$ nicht regulär. Formal: existiert kein $n$, so dass alle langen Wörter eine gute Zerlegung besitzen, dann ist $L$ nicht regulär. Die Negation liest sich:

$$\forall\, n \geq 1\; \exists\, w \in L,\, |w| \geq n\; \forall\, x,y,z\;\text{mit}\;w=xyz,\,|xy|\leq n,\,|y|\geq 1:\; \exists\, i \geq 0:\; xy^i z \notin L$$

Anschauung: Warum gilt das Lemma?

Ein DEA mit $n$ Zuständen, der ein Wort $w$ mit $|w| \geq n$ akzeptiert, muss beim Lesen der ersten $n$ Zeichen einen Zustand zweimal besuchen (Schubfachprinzip). Der Teil dazwischen ist eine Schleife $y$ — und Schleifen kann man beliebig oft durchlaufen (pumpen).

Wichtige Nicht-Aussage

Das Pumping-Lemma ist notwendig, aber nicht hinreichend. Es gibt nicht-reguläre Sprachen, die die Pumping-Eigenschaft trotzdem erfüllen. Ein bestandener Pumping-Test beweist also keine Regularität — er widerlegt nur nicht.

2 · Kernkonzepte & Vorgehen

Der Beweis dass eine Sprache $L$ nicht regulär ist, folgt einem festen Schema. Die Quantoren-Reihenfolge ist der Kern und wird in der Klausur streng bewertet.

Annahme: Angenommen, $L$ ist regulär. Dann existiert eine Pumping-Zahl $n$. Man kennt $n$ nicht — es ist beliebig.
Wortwahl: Wähle ein konkretes $w \in L$ mit $|w| \geq n$. Das Wort hängt typischerweise von $n$ ab, z.B. $w = a^n b^n$. Die Wahl ist der kreative Schritt.
Zerlegung: Betrachte jede beliebige Zerlegung $w = xyz$ mit $|xy| \leq n$ und $|y| \geq 1$. Man muss alle möglichen Zerlegungen abdecken — meist reicht eine Fallunterscheidung, weil die Bedingung $|xy| \leq n$ die möglichen Formen von $y$ stark einschränkt.
Pumpen: Wähle ein $i$ (typisch $i = 0$ oder $i = 2$) und zeige, dass $xy^i z \notin L$. Es reicht ein problematisches $i$.
Widerspruch: Das widerspricht Punkt 3 des Lemmas. Also war die Annahme falsch; $L$ ist nicht regulär.

Quantoren-Merke

Das Lemma liest sich als $\exists\, n\; \forall\, w\; \exists\, (x,y,z)\; \forall\, i$. Als Beweisführer bist du in der widerlegenden Position: du hast die Wahl von $w$ und $i$, aber die Zerlegung ist dir gegeben — du musst alle Fälle behandeln. Merksatz: Wort wählen — Zerlegung erdulden — $i$ wählen.

3 · Beispiel durchgerechnet

Behauptung: $L = \{ a^n b^n : n \geq 0 \}$ ist nicht regulär.

Beweis (per Widerspruch mit Pumping-Lemma):

Angenommen, $L$ ist regulär. Dann existiert nach dem Pumping-Lemma eine Pumping-Zahl $n \geq 1$.
Wähle das Wort $w = a^n b^n$. Es gilt $w \in L$ und $|w| = 2n \geq n$. Also muss eine Zerlegung $w = xyz$ existieren mit $|xy| \leq n$, $|y| \geq 1$ und $xy^i z \in L$ für alle $i \geq 0$.
Analyse der Zerlegung. Weil $|xy| \leq n$ und die ersten $n$ Zeichen von $w$ ausschließlich $a$ sind, liegen $x$ und $y$ vollständig im $a$-Block. Also: $$x = a^p,\quad y = a^q,\quad z = a^{n-p-q} b^n$$ mit $p \geq 0$, $q \geq 1$, $p + q \leq n$.
Pumpen mit $i = 2$. Betrachte $$xy^2 z = a^p \cdot a^{2q} \cdot a^{n-p-q} b^n = a^{n+q} b^n$$ Da $q \geq 1$, ist die Anzahl der $a$s echt größer als die Anzahl der $b$s. Also $xy^2 z \notin L$.
Widerspruch zum Pumping-Lemma (Punkt 3). Also war die Annahme falsch: $L$ ist nicht regulär. $\square$

Alternative mit $i = 0$

Man könnte auch $xy^0 z = a^{n-q} b^n$ betrachten. Da $q \geq 1$, wieder ungleiche Anzahl von $a$ und $b$. Beide Wahlen führen zum Widerspruch — es reicht eine.

Skizze: Warum das Schubfachprinzip greift

     Zustände eines hypothetischen DEA für L (|Q| = n)

     -- a -- a -- a -- ... -- a -- b -- b -- ... -- b --> akzeptiert
        |                    |
        \-- innerhalb der ersten n Zeichen wird ein
            Zustand zweimal besucht  ->  Schleife y
            (das ist genau der pumpbare Teil)

4 · Rechenaufgaben mit Lösung

Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen und Schritt für Schritt vergleichen. Alle Beweise folgen dem strengen Schema Annahme → Wortwahl → Zerlegung analysieren → Fälle → Pumpen → Widerspruch.

Aufgabe 1 leicht · Klassiker

Zeige mit dem Pumping-Lemma, dass die Sprache $$L_1 = \{ a^n b^n : n \geq 0 \}$$ über dem Alphabet $\Sigma = \{a, b\}$ nicht regulär ist. Führe den Beweis in allen fünf Standard-Schritten aus.

Lösung anzeigen

Schritt 1 — Annahme: Angenommen, $L_1$ ist regulär. Nach dem Pumping-Lemma existiert eine Pumping-Zahl $n \geq 1$, so dass jedes Wort $w \in L_1$ mit $|w| \geq n$ eine Zerlegung $w = xyz$ mit den drei Pumping-Eigenschaften besitzt.

Schritt 2 — Wortwahl: Wähle $w = a^n b^n$. Dann gilt $w \in L_1$ und $|w| = 2n \geq n$. Diese Wahl hängt bewusst von $n$ ab, weil $n$ als beliebig groß gedacht werden muss.

Schritt 3 — Zerlegung analysieren: Sei $w = xyz$ eine beliebige Zerlegung mit $|xy| \leq n$ und $|y| \geq 1$. Da die ersten $n$ Zeichen von $w$ ausschließlich $a$s sind, liegen $x$ und $y$ vollständig im $a$-Block. Es folgt $$x = a^p,\quad y = a^q,\quad z = a^{n-p-q} b^n$$ mit $p \geq 0$, $q \geq 1$ und $p + q \leq n$. Es gibt hier keine Fallunterscheidung — jede zulässige Zerlegung hat exakt diese Form.

Schritt 4 — Pumpen mit $i = 2$: $$xy^2 z = a^p \cdot (a^q)^2 \cdot a^{n-p-q} b^n = a^{p + 2q + n - p - q} b^n = a^{n+q} b^n$$ Wegen $q \geq 1$ gilt $n + q \neq n$, also stimmen $a$- und $b$-Anzahl nicht überein und damit $xy^2 z \notin L_1$.

Schritt 5 — Widerspruch: Das steht im Widerspruch zur Pumping-Eigenschaft $\forall i \geq 0: xy^i z \in L_1$. Die Annahme war falsch.

Ergebnis: $L_1 = \{a^n b^n : n \geq 0\}$ ist nicht regulär. $\square$

Aufgabe 2 mittel · Fallunterscheidung

Zeige, dass die Sprache der Verdoppelungen $$L_2 = \{ ww : w \in \{a,b\}^* \}$$ nicht regulär ist. Achte auf eine geschickte Wortwahl, damit $y$ zwingend in eine bestimmte Position fällt.

Lösung anzeigen

Schritt 1 — Annahme: Angenommen, $L_2$ ist regulär mit Pumping-Zahl $n \geq 1$.

Schritt 2 — Wortwahl: Wähle $u = a^n b$ und betrachte $$w = u \cdot u = a^n b\, a^n b \in L_2, \quad |w| = 2n + 2 \geq n$$ Die entscheidende Idee: das $b$ in der Mitte fixiert die Trennstelle der beiden Kopien. Manipulationen im ersten $a$-Block zerstören die Verdopplungsstruktur.

Schritt 3 — Zerlegung analysieren: Sei $w = xyz$ mit $|xy| \leq n$ und $|y| \geq 1$. Da die ersten $n$ Zeichen von $w$ alle $a$ sind, liegen $x, y$ komplett im vorderen $a$-Block: $$x = a^p,\quad y = a^q,\quad z = a^{n-p-q}\, b\, a^n b$$ mit $p \geq 0$, $q \geq 1$, $p + q \leq n$.

Schritt 4 — Pumpen mit $i = 2$: $$xy^2 z = a^{n+q}\, b\, a^n\, b$$ Angenommen dieses Wort läge in $L_2$, also gäbe es ein $v$ mit $xy^2 z = v v$. Wegen $|xy^2 z| = 2n + q + 2$ und ungerader Parität für ungerades $q$ scheitert das direkt für ungerades $q$. Für allgemeines $q$ argumentiert man strukturell: die beiden Hälften müssten die Länge $n + q/2 + 1$ haben und je genau ein $b$ enthalten. Das eine $b$ liegt an Position $n + q + 1$, das andere an Position $2n + q + 2$. Der Abstand ist $n + 1$, gleichzeitig muss der Abstand aber $|v| = (2n + q + 2)/2$ betragen. Aus $n + 1 = n + q/2 + 1$ folgte $q = 0$ — Widerspruch zu $q \geq 1$.

Schritt 5 — Widerspruch: Für kein $q \geq 1$ ist $xy^2 z$ eine Verdopplung. Also $xy^2 z \notin L_2$, ein Widerspruch zum Pumping-Lemma.

Ergebnis: $L_2 = \{ww : w \in \{a,b\}^*\}$ ist nicht regulär. $\square$

Aufgabe 3 schwer · Wachstumsargument

Zeige mit dem Pumping-Lemma, dass die Sprache der Quadrate $$L_3 = \{ a^{n^2} : n \geq 0 \}$$ nicht regulär ist. Nutze aus, dass die Lücken zwischen aufeinanderfolgenden Quadratzahlen beliebig groß werden.

Lösung anzeigen

Schritt 1 — Annahme: Angenommen, $L_3$ ist regulär mit Pumping-Zahl $n \geq 1$. Zur Klarheit nennen wir diese Konstante ab jetzt $p$ (statt $n$), um Verwechslung mit dem Index der Quadratzahl zu vermeiden. Also: Pumping-Zahl $p \geq 1$.

Schritt 2 — Wortwahl: Wähle $w = a^{p^2}$. Es gilt $w \in L_3$ und $|w| = p^2 \geq p$.

Schritt 3 — Zerlegung analysieren: Sei $w = xyz$ mit $|xy| \leq p$, $|y| \geq 1$. Da $w$ ein reines $a$-Wort ist, gilt $y = a^q$ für ein $q$ mit $1 \leq q \leq p$.

Schritt 4 — Pumpen mit $i = 2$: $$xy^2 z = a^{p^2 + q}$$ Damit dieses Wort in $L_3$ läge, müsste $p^2 + q$ eine Quadratzahl sein, also $p^2 + q = m^2$ für ein $m \in \mathbb{N}$. Die nächste Quadratzahl nach $p^2$ ist $(p+1)^2 = p^2 + 2p + 1$. Zwischen $p^2$ und $(p+1)^2$ liegen keine weiteren Quadratzahlen. Es müsste also gelten $$q \geq 2p + 1$$ Das widerspricht aber $q \leq p$.

Schritt 5 — Widerspruch: Für kein zulässiges $q$ ist $p^2 + q$ eine Quadratzahl. Also $xy^2 z \notin L_3$ — Widerspruch zum Pumping-Lemma.

Ergebnis: $L_3 = \{a^{n^2} : n \geq 0\}$ ist nicht regulär. Das Argument verallgemeinert sich auf alle Sprachen mit Wortlängen, deren aufeinanderfolgende Lücken über jede Konstante hinauswachsen (z.B. auch $\{a^{2^n}\}$, Primzahllängen). $\square$

Aufgabe 4 mittel · Anfängerfehler analysieren

Ein Kommilitone versucht folgenden Beweis für $L_1 = \{a^n b^n : n \geq 0\}$:

Sei $n$ die Pumping-Zahl. Wähle $w = ab \in L_1$. Dann ist $|w| = 2$. Wir zerlegen $w = x\,y\,z$ mit $x = \varepsilon$, $y = a$, $z = b$ und pumpen mit $i = 2$: $xy^2 z = aab \notin L_1$. Widerspruch — also nicht regulär.

Erkläre präzise, an welchen Stellen dieser Beweis kaputt ist. Nenne mindestens zwei Fehler.

Lösung anzeigen

Schritt 1 — Fehler A (falsche Wortlänge): Das Pumping-Lemma verlangt $|w| \geq n$. Hier wurde $|w| = 2$ gewählt. Da $n$ die Pumping-Zahl von $L_1$ ist und beliebig groß sein kann (z.B. $n = 47$), ist die Bedingung $|w| \geq n$ mit $w = ab$ nicht garantiert. Der Prüfling hat $n$ implizit auf $\leq 2$ festgelegt — unzulässig.

Schritt 2 — Fehler B (Zerlegung selbst gewählt): Das Lemma sagt, dass irgendeine Zerlegung mit den drei Eigenschaften existiert. Der Prüfling darf die Zerlegung nicht selbst wählen — er muss alle zulässigen Zerlegungen widerlegen. Hier wurde bequem $y = a$ gesetzt. Für einen sauberen Beweis müsste stattdessen argumentiert werden: Für jede beliebige Zerlegung mit $|xy| \leq n$ und $|y| \geq 1$ gilt \dots

Schritt 3 — Fehler C (Wort nicht in Abhängigkeit von $n$): Die Wortwahl soll von $n$ skalieren, damit $|w| \geq n$ automatisch erfüllt ist. Standardwahl: $w = a^n b^n$, nicht $w = ab$.

Schritt 4 — Was wäre richtig gewesen: $$w = a^n b^n,\quad \text{beliebige Zerlegung } w = xyz \text{ mit } |xy| \leq n, |y| \geq 1$$ Daraus folgt $y = a^q$ mit $q \geq 1$ (siehe Aufgabe 1). Pumpen liefert $xy^2 z = a^{n+q} b^n \notin L_1$ — Widerspruch.

Ergebnis: Der Beweis des Kommilitonen ist an drei Stellen kaputt: Wortlänge, Zerlegungswahl, fehlende Skalierung mit $n$. In der Klausur würde dieser Beweis mit voller Punktzahl abgezogen, obwohl die Aussage nicht regulär selbst korrekt ist.

Aufgabe 5 mittel · Bedingung $|y| \geq 1$

Ein anderer Prüfling führt einen Beweis für $L_1 = \{a^n b^n\}$ und schreibt in Schritt 3:

Wähle $y = \varepsilon$. Dann ist $xy^0 z = xz = w$ und $xy^2 z = xz = w$, also $xy^i z \in L_1$ für alle $i$. Kein Widerspruch — das Lemma ist erfüllt.

Wo liegt der Fehler? Zeige, warum $y$ kann leer sein ein grundlegender Denkfehler ist, und leite daraus eine kurze Merkregel ab.

Lösung anzeigen

Schritt 1 — Bedingung des Lemmas lesen: Das Pumping-Lemma fordert explizit $|y| \geq 1$. Die Zerlegung $w = xyz$ mit $y = \varepsilon$ ist damit keine gültige Pumping-Zerlegung — sie erfüllt Bedingung (2) nicht.

Schritt 2 — Warum ist $|y| \geq 1$ nötig? Die Beweisidee des Lemmas nutzt die Schleife im DEA: der Zustand, der doppelt besucht wird, definiert eine echte Schleife im Automaten. Eine leere Schleife wäre keine Schleife. Formal: das Schubfachargument liefert zwei verschiedene Positionen $0 \leq i < j \leq n$, an denen derselbe Zustand steht — der Ausschnitt $w[i+1..j]$ hat Länge $j - i \geq 1$.

Schritt 3 — Konsequenz für den Beweis: Der Prüfling darf niemals sagen ich wähle $y = \varepsilon$. Wenn man alle zulässigen Zerlegungen betrachtet, ist die leere Zerlegung von vornherein ausgeschlossen. Genau darin liegt der Widerspruchsangriff: das Wort $y$ ist echt nicht-leer, also ändert sich durch Pumpen die Länge tatsächlich.

Schritt 4 — Rechenbeispiel: Für $w = a^n b^n$ und Zerlegung $y = a^q$ mit $q \geq 1$: $$|xy^2 z| = |w| + q = 2n + q > 2n = |w|$$ Der zusätzliche Beitrag $q \geq 1$ ist genau der Hebel, der das Ungleichgewicht zwischen $a$s und $b$s erzeugt. Ohne $q \geq 1$ wäre $|xy^2 z| = |w|$ und der Widerspruch fiele weg.

Schritt 5 — Merkregel: Y ist nie leer. Wenn im Lauf des Beweises die Möglichkeit $y = \varepsilon$ auftaucht, ist entweder die Zerlegung falsch begründet oder die Bedingung $|y| \geq 1$ wurde vergessen.

Ergebnis: Die Bedingung $|y| \geq 1$ ist keine Zusatzbedingung, sondern das Herzstück des Lemmas. Ohne sie wäre die Aussage trivial (jeder Zustand wird 0-mal besucht) und liefe leer.

Aufgabe 6 mittel · Palindrome

Zeige, dass die Sprache aller Palindrome über $\{a, b\}$ $$L_4 = \{ w \in \{a,b\}^* : w = w^R \}$$ nicht regulär ist. Hier bezeichnet $w^R$ das gespiegelte Wort. Wähle das Wort so, dass beide Ränder durch $b$ markiert sind.

Lösung anzeigen

Schritt 1 — Annahme: $L_4$ sei regulär mit Pumping-Zahl $n \geq 1$.

Schritt 2 — Wortwahl: Wähle $$w = a^n\, b\, a^n \in L_4$$ Es gilt $|w| = 2n + 1 \geq n$ und $w = w^R$, weil die Struktur symmetrisch ist.

Schritt 3 — Zerlegung analysieren: Sei $w = xyz$ mit $|xy| \leq n$, $|y| \geq 1$. Wieder liegen $x, y$ vollständig im ersten $a$-Block, also $$x = a^p,\quad y = a^q,\quad z = a^{n-p-q}\, b\, a^n$$ mit $q \geq 1$.

Schritt 4 — Pumpen mit $i = 2$: $$xy^2 z = a^{n+q}\, b\, a^n$$ Damit dies ein Palindrom wäre, müsste $a^{n+q} b a^n = (a^{n+q} b a^n)^R = a^n b a^{n+q}$ gelten. Zeichenweiser Vergleich der Position 1 (bzw. Position $|w|$): links steht $a$, aber die entsprechende gespiegelte Position im rechten Block hat nach $q$ zusätzlichen $a$s eine andere Zeichenverteilung. Konkret: die Position des einzigen $b$ ist links $n + q + 1$, rechts (im gespiegelten Wort) an Position $n + 1$. Da $q \geq 1$, sind diese Positionen verschieden — kein Palindrom.

Schritt 5 — Widerspruch: $xy^2 z \notin L_4$, im Widerspruch zum Pumping-Lemma.

Ergebnis: $L_4 = \{w \in \{a,b\}^* : w = w^R\}$ ist nicht regulär. $\square$

Aufgabe 7 schwer · Primzahlen

Zeige, dass die Sprache $$L_5 = \{ a^p : p \text{ ist Primzahl} \}$$ nicht regulär ist. Nutze aus, dass Vielfache von zusammengesetzten Zahlen niemals prim sind.

Lösung anzeigen

Schritt 1 — Annahme: $L_5$ sei regulär mit Pumping-Zahl $n \geq 1$.

Schritt 2 — Wortwahl: Wähle eine Primzahl $p \geq n + 2$ (existiert nach Euklid) und setze $w = a^p$. Dann $w \in L_5$ und $|w| = p \geq n$.

Schritt 3 — Zerlegung analysieren: Sei $w = xyz$ mit $|xy| \leq n$, $|y| \geq 1$. Also $y = a^q$ mit $1 \leq q \leq n$. Die restlichen Zeichen sind $x = a^{p_1}$, $z = a^{p_2}$ mit $p_1 + q + p_2 = p$.

Schritt 4 — Pumpen mit $i = p + 1$: $$|xy^{p+1} z| = p_1 + (p+1)\,q + p_2 = (p - q) + (p+1)\,q = p + p\,q = p(1 + q)$$ Da $p \geq 2$ (Primzahl) und $1 + q \geq 2$, ist $p(1+q)$ Produkt zweier Faktoren, beide $\geq 2$ — also keine Primzahl.

Schritt 5 — Widerspruch: $xy^{p+1} z$ hat zusammengesetzte Länge, also $xy^{p+1} z \notin L_5$. Widerspruch.

Ergebnis: $L_5 = \{a^p : p \text{ prim}\}$ ist nicht regulär. Das ist ein besonders elegantes Beispiel, weil das Pump-$i$ vom Wort selbst abhängt. $\square$

Aufgabe 8 mittel · Wortwahl-Analyse

Für die Sprache $L_1 = \{a^n b^n\}$ werden vier Vorschläge für das Pumping-Wort diskutiert. Fülle die Tabelle aus, welche funktionieren und warum jeweils.

Vorschlag	funktioniert?	Grund
$w = ab$	?	?
$w = a^n b^n$	?	?
$w = b^n a^n$	?	?
$w = a^{2n} b^{2n}$	?	?

Lösung anzeigen

Schritt 1 — Vorschlag $w = ab$: Scheitert an $|w| \geq n$. Für $n \geq 3$ ist $|w| = 2 < n$, das Lemma ist gar nicht anwendbar auf dieses Wort. Nicht geeignet.

Schritt 2 — Vorschlag $w = a^n b^n$: Erfüllt $w \in L_1$ und $|w| = 2n \geq n$. Die Bedingung $|xy| \leq n$ zwingt $y$ in den $a$-Block. Pumpen verletzt die Balance — Widerspruch geht auf. Standardwahl, funktioniert.

Schritt 3 — Vorschlag $w = b^n a^n$: Liegt nicht in $L_1$, denn $L_1$ verlangt erst $a$s, dann $b$s. Ein Beweis darf nur mit $w \in L$ arbeiten. Nicht geeignet.

Schritt 4 — Vorschlag $w = a^{2n} b^{2n}$: Es gilt $w \in L_1$ (mit Faktor 2 im Exponenten der Definition) und $|w| = 4n \geq n$. Analyse: $|xy| \leq n$ zwingt $y = a^q$ mit $q \geq 1$, Pumpen mit $i = 2$ liefert $a^{2n+q} b^{2n} \notin L_1$. Funktioniert ebenfalls, aber unnötig aufwendig — $a^n b^n$ ist die schlanke Wahl.

Ergebnis:

Vorschlag	funktioniert?	Grund
$w = ab$	nein	$\|w\| \geq n$ nicht garantiert
$w = a^n b^n$	ja	skaliert mit $n$, saubere Struktur — Standard
$w = b^n a^n$	nein	$w \notin L_1$
$w = a^{2n} b^{2n}$	ja	funktioniert, aber unnötig groß

5 · Typische Klausurfragen (Lesen!)

Typ A: Beweis lesen und beurteilen

Ein Beweis-Text ist gegeben. Aufgabe: Ist er korrekt? Wenn nein, wo liegt der Fehler? Häufige Fallen: falsche Wahl der Quantoren (der Prüfling wählt $y$, obwohl er es nicht darf), Wortwahl von einer festen Zahl statt von $n$, Pumpen von $i = 1$ (trivial wahr), oder $|xy| \leq n$ übersehen.

Typ B: Wortwahl begründen

Es wird gefragt: Warum ist $w = a^n b^n$ die richtige Wahl, aber $w = ab$ nicht? Antwort: $|w| \geq n$ muss gelten, und $n$ ist beliebig groß. Ein festes Wort funktioniert nicht.

Typ C: Zerlegung diskutieren

Gegeben ein Wort und eine Zerlegung, entscheide: erfüllt sie $|xy| \leq n$ und $|y| \geq 1$? Wenn ja, was passiert beim Pumpen? Hier zählt genaues Ablesen der Indizes.

Typ D: Sprache klassifizieren

Eine Sprache ist gegeben (z.B. $L = \{ a^i b^j : i \neq j \}$). Frage: regulär oder nicht, mit Begründung. Manchmal ist Abschlusseigenschaften-Argument einfacher als direktes Pumpen (z.B. Komplement, Schnitt mit $a^* b^*$).

Falle: Pumping-Lemma umgekehrt

Wenn eine Sprache das Lemma erfüllt, folgt nicht, dass sie regulär ist. In der Klausur nie schreiben: Da wir pumpen können, ist $L$ regulär. Das ist falsch.

6 · Fragen zum Selbsttest

1. Nenne die drei formalen Bedingungen des Pumping-Lemmas für reguläre Sprachen.

Für $w = xyz$ gelten: (1) $|xy| \leq n$, (2) $|y| \geq 1$, (3) für alle $i \geq 0$ gilt $xy^i z \in L$. Die Pumping-Zahl $n$ hängt von $L$ ab und ist mindestens 1.

2. Warum reicht es, ein einziges $i$ mit $xy^i z \notin L$ zu finden, um Widerspruch zu zeigen?

Punkt (3) des Lemmas fordert für alle $i \geq 0$. Wird auch nur ein einziges Gegenbeispiel gefunden, ist die All-Aussage verletzt und damit die gesamte Konjunktion des Lemmas für dieses $w$. Zusammen mit der All-Aussage über Wörter liefert das den Widerspruch.

3. Was ist der typische Fehler bei der Wahl von $y$?

Der Prüfling wählt sich eine bequeme Zerlegung selbst (z.B. $y = ab$). Das ist unzulässig: die Zerlegung ist durch das Lemma gegeben, man muss alle zulässigen Zerlegungen betrachten. Man wählt nur das Wort $w$ und das $i$.

4. Warum funktioniert die Wortwahl $w = a^n b^n$ für $L = \{a^n b^n\}$ so gut?

Weil $|xy| \leq n$ erzwingt, dass $y$ vollständig im $a$-Block liegt. Damit ist die Struktur von $y$ stark eingeschränkt (nur $a$s), und das Pumpen erzeugt sofort einen Ungleichgewichtszustand.

5. Ist $L = \{a^n b^m : n, m \geq 0\}$ regulär?

Ja. Der reguläre Ausdruck $a^* b^*$ beschreibt $L$. Das Pumping-Lemma ist hier erfüllt (z.B. mit $n = 1$). Man muss die beiden Sprachen $\{a^n b^n\}$ und $\{a^n b^m\}$ genau unterscheiden — der Unterschied liegt in der Kopplung der Exponenten.

6. Zeige knapp: $L = \{ww : w \in \{a,b\}^*\}$ ist nicht regulär.

Wähle $u = a^n b$ und $w' = uu = a^n b a^n b$. Wegen $|xy| \leq n$ liegt $y$ im ersten $a$-Block, also $y = a^q$ mit $q \geq 1$. Pumpen mit $i = 2$ ergibt $a^{n+q} b a^n b$. Damit dieses Wort in $L$ läge, müsste es sich als $vv$ schreiben lassen — was wegen der ungleichen Blocklängen unmöglich ist. Widerspruch.

7. Erkläre den Unterschied zwischen den beiden Aussagen: das Lemma ist verletzt vs. das Lemma ist nicht anwendbar.

Verletzt: es gibt keine Pumping-Zahl, für die alle langen Wörter eine gute Zerlegung besitzen — daraus folgt Nicht-Regularität. Nicht anwendbar ist keine formale Aussage; das Lemma gilt für alle regulären Sprachen. Man wendet es also immer im Kontrapositions-Modus an.

8. Welche Rolle spielt das Schubfachprinzip im Beweis des Pumping-Lemmas?

Ein DEA hat endlich viele Zustände. Liest er ein Wort mit mehr Zeichen als Zuständen, muss er nach dem Schubfachprinzip einen Zustand mindestens zweimal besuchen. Der Teil der Eingabe zwischen den zwei Besuchen ist eine Schleife im Automaten und entspricht dem pumpbaren Teilwort $y$.

9. Ein Kommilitone schreibt: Wir wählen $y = ab$ und pumpen. Warum ist das falsch?

Weil $y$ nicht frei wählbar ist. Das Lemma sagt nur, dass irgendeine Zerlegung existiert, nicht welche. Für den Widerspruchsbeweis muss der Prüfling alle zulässigen Zerlegungen abdecken (oft per Fallunterscheidung), nicht eine passende auswählen.

10. $L = \{a^p : p \text{ prim}\}$ — Skizze warum nicht regulär.

Angenommen regulär mit Pumping-Zahl $n$. Wähle eine Primzahl $p \geq n$ und $w = a^p$. Jede Zerlegung hat $y = a^q$ mit $1 \leq q \leq n$. Pumpen mit $i = p+1$ ergibt $xy^{p+1} z$ der Länge $p + p \cdot q = p(1+q)$ — ein zusammengesetztes Produkt und damit keine Primzahllänge. Widerspruch.

7 · Dos & Don'ts in der Klausur

Do — Quantoren offenlegen Formuliere den Beweis wörtlich: Sei $n$ die Pumping-Zahl. Wähle $w = \dots$ Für jede Zerlegung $\dots$ betrachte $i = 2$. Die Reihenfolge signalisiert dem Korrektor, dass du das Lemma verstanden hast.

Don't — $y$ selbst wählen Niemals Wir wählen $y = a$. Die Zerlegung ist vorgegeben; du behandelst alle möglichen Formen von $y$, meist per Fallunterscheidung anhand von $|xy| \leq n$.

Do — $|xy| \leq n$ ausnutzen Diese Bedingung ist meist der Hebel: sie fixiert, in welchem Präfix von $w$ die Schleife liegen muss.

Don't — Pumping-Lemma umgekehrt Aus $L$ erfüllt das Lemma folgt nicht $L$ ist regulär. Das Lemma ist nur notwendig.

Do — Wort in Abhängigkeit von $n$ wählen Ein gutes Klausur-Wort skaliert mit $n$: $a^n b^n$, $a^{n!}$, $a^n b a^n$.

Don't — $i = 1$ pumpen Für $i = 1$ gilt trivial $xy^1 z = w \in L$. Das liefert nie einen Widerspruch. Nutze $i = 0$ oder $i \geq 2$.

Do — Fallunterscheidung, wenn nötig Bei Wörtern über gemischten Alphabeten (z.B. $a^n b^n a^n$) alle möglichen Positionen von $y$ auflisten und jeden Fall zum Widerspruch führen.

Don't — Beweis mit konkretem $n$ Niemals Sei $n = 5$. $n$ ist gegeben, aber unbekannt. Der Beweis muss für jedes hypothetische $n$ funktionieren.