Pumping-Lemma für reguläre Sprachen

Du weißt, dass ein DFA aⁿ bⁿ nicht erkennen kann, weil er nicht beliebig weit zählen kann. Aber wie beweist man das sauber? Das Pumping-Lemma ist das Standardwerkzeug der Klausur, um zu zeigen, dass eine Sprache nicht regulär ist.

Was du können musst:

• das Pumping-Lemma formal aufschreiben (Quantoren-Reihenfolge)
• den Nicht-Regularitäts-Beweis als Gegenspieler-Spiel führen
• den Klassiker \aⁿ bⁿ\ als nicht regulär beweisen
• die häufigen Fallen (Lemma-Richtung, Wortwahl, Zerlegung) vermeiden

Die Idee in einem Satz

Jede reguläre Sprache hat eine Zahl p (Pumping-Länge), sodass sich jedes hinreichend lange Wort w ∈ L so in drei Teile w = xyz zerlegen lässt, dass man den mittleren Teil y beliebig oft wiederholen ("pumpen") kann und immer in L bleibt.

Warum gilt das? (Schubfachprinzip)

Ein DFA hat endlich viele Zustände, sagen wir p. Liest er ein Wort der Länge ≥ p, so durchläuft er mindestens p+1 Zustände und muss daher einen Zustand wiederholen (Schubfachprinzip). Zwischen den beiden Besuchen liegt eine Schleife, das ist der Teil y. Diese Schleife kann man 0-mal, 1-mal, 2-mal, beliebig oft durchlaufen, und landet immer im selben Endzustand. Genau das ist das Pumpen.

Das Lemma formal

Ist L regulär, dann gibt es ein p ≥ 1, sodass für jedes w ∈ L mit |w| ≥ p eine Zerlegung w = xyz existiert mit:

1. |xy| ≤ p
2. |y| ≥ 1 (also y ≠ ε)
3. x yⁱ z ∈ L für alle i ≥ 0

Wichtig: Das Lemma ist eine notwendige, keine hinreichende Bedingung. Es beweist nur Nicht-Regularität (durch Verletzung), niemals Regularität.

Der Beweis als Gegenspieler-Spiel

Um zu zeigen, dass L nicht regulär ist, führt man einen Widerspruchsbeweis. Stell ihn dir als Spiel vor, bei dem du gewinnen musst, egal was der Gegner tut:

Der Hebel ist Bedingung |xy| ≤ p: sie zwingt y in den vorderen Teil des Wortes, sodass du genau weißt, woraus y besteht.

Klassiker: \aⁿ bⁿ mid n ≥ 1\ ist nicht regulär

• Du wählst w = a^p b^p (das ist in L, und |w| = 2p ≥ p).
• Der Gegner zerlegt w = xyz mit |xy| ≤ p. Da die ersten p Zeichen alle a sind, besteht y nur aus a, also y = a^k mit k ≥ 1.
• Du pumpst i = 2: x y² z = a^(p+k) b^p. Jetzt sind es p+k mal a, aber nur p mal b. Wegen k ≥ 1 ist die Anzahl ungleich, also x y² z ∉ L.
• Widerspruch. Damit ist \aⁿ bⁿ\ nicht regulär.

Probier es aus

Schalte zwischen einer regulären Sprache (in der Pumpen immer drinbleibt) und aⁿ bⁿ (wo Pumpen die Balance zerstört). Zieh den Pump-Exponenten i und beobachte, ob das Ergebnis x yⁱ z noch in der Sprache liegt.

Klausur-Faustregeln

1. Richtung beachten. Das Pumping-Lemma beweist Nicht-Regularität (per Widerspruch), niemals Regularität.

2. Quantoren-Reihenfolge. p ist gegeben, du wählst w, der Gegner wählt die Zerlegung, du wählst i. Wer was wählt, entscheidet den Beweis.

3. w abhängig von p wählen. Nimm w = a^p b^p, nicht ein festes Wort wie aabb.

4. |xy| ≤ p als Hebel nutzen. Diese Bedingung zwingt y in einen bekannten Block (bei a^p b^p in die a).

5. Meist reicht i = 0 oder i = 2. Ein einziges i, das aus L herausführt, genügt für den Widerspruch.

6. Es gibt auch ein Pumping-Lemma für kontextfreie Sprachen (mit Zerlegung uvxyz), um z.B. \aⁿ bⁿ cⁿ\ als nicht kontextfrei zu zeigen.

Häufige Stolpersteine

1. Lemma-Richtung verwechseln. Wenn ein Wort sich pumpen lässt, beweist das nichts. Nur eine Verletzung (ein i führt aus L heraus) beweist Nicht-Regularität.

2. w fest wählen. w muss von p abhängen. Ein festes aabb hilft nicht, wenn p größer ist.

3. Die Zerlegung selbst günstig wählen. Du darfst die Zerlegung nicht bestimmen, der Gegner tut das. Dein Argument muss für jede zulässige Zerlegung gelten, abgesichert durch |xy| ≤ p.

4. |xy| ≤ p ignorieren. Ohne diese Bedingung weißt du nicht, woraus y besteht, der Beweis bricht zusammen.

5. |y| ≥ 1 vergessen. y darf nicht leer sein, sonst ändert Pumpen nichts.

6. Das Lemma für eine Äquivalenz halten. Es ist nur notwendig für Regularität. Es gibt nicht-reguläre Sprachen, die das Pumping-Lemma trotzdem erfüllen (dann braucht man stärkere Werkzeuge wie den Satz von Myhill-Nerode).

Pumpen, bis es bricht

Spiele den Beweis durch. Bei aⁿ bⁿ liegt der pumpbare Block y wegen |xy| ≤ p komplett im a-Teil, jedes i ≠ 1 zerstört die Balance. Bei der regulären Sprache bleibt das Wort dagegen für jedes i gültig.

Klausur-Tipp: Schreibe im Beweis immer explizit hin, warum y nur aus a besteht ("wegen |xy| ≤ p und weil die ersten p Zeichen alle a sind"). Genau dieser Satz bringt die Punkte.