Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Du weißt, dass ein DFA 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:
Klausur-Tipp: Schreibe im Beweis immer explizit hin, warum nur aus besteht ("wegen und weil die ersten Zeichen alle sind"). Genau dieser Satz bringt die Punkte.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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:
\aⁿ bⁿ\ als nicht regulär beweisenJede reguläre Sprache hat eine Zahl
p(Pumping-Länge), sodass sich jedes hinreichend lange Wortw ∈ Lso in drei Teilew = xyzzerlegen lässt, dass man den mittleren Teilybeliebig oft wiederholen ("pumpen") kann und immer inLbleibt.
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.
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:
|xy| ≤ p|y| ≥ 1 (also y ≠ ε)x yⁱ z ∈ L für alle i ≥ 0Wichtig: Das Lemma ist eine notwendige, keine hinreichende Bedingung. Es beweist nur Nicht-Regularität (durch Verletzung), niemals Regularität.
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:
| Schritt | Wer? | Was? |
|---|---|---|
| 1 | Annahme | L ist regulär, also existiert eine Pumping-Länge p. |
| 2 | Gegner | gibt ein konkretes p vor (du kennst es nicht). |
| 3 | Du | wählst geschickt ein Wort w ∈ L mit ` |
| 4 | Gegner | zerlegt w = xyz mit ` |
| 5 | Du | findest ein i ≥ 0 mit x yⁱ z ∉ L. |
| 6 | Schluss | Widerspruch zu Bedingung 3, also war die Annahme falsch: L ist nicht regulär. |
Der Hebel ist Bedingung |xy| ≤ p: sie zwingt y in den vorderen Teil des Wortes, sodass du genau weißt, woraus y besteht.
\aⁿ bⁿ mid n ≥ 1\ ist nicht regulärw = a^p b^p (das ist in L, und |w| = 2p ≥ p).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.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.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.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
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.
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).
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.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
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.
Klausurfragen mit Lösungen (6)
Antwort: Um zu beweisen, dass eine Sprache NICHT regulär ist
Erklärung: Das Pumping-Lemma ist eine notwendige Bedingung für Regularität. Verletzt eine Sprache das Lemma, ist sie nicht regulär. Es kann Regularität NICHT beweisen.
Antwort: `|xy| ≤ p`, `|y| ≥ 1` und `x yⁱ z ∈ L` für alle `i ≥ 0`
Erklärung: Die drei Bedingungen sind: (1) `|xy| ≤ p`, (2) `|y| ≥ 1`, (3) für alle `i ≥ 0` ist `x yⁱ z ∈ L`. Bedingung 1 ist der Hebel, Bedingung 3 die pumpbare Eigenschaft.
Antwort: `y` besteht nur aus `a`
Erklärung: Die ersten `p` Zeichen von `a^p b^p` sind alle `a`. Wegen `|xy| ≤ p` liegt der ganze Block `xy` (und damit `y`) in diesem `a`-Bereich, also `y = a^k` mit `k ≥ 1`.
Antwort: Falsch
Erklärung: Falsch. Das Pumping-Lemma ist nur notwendig, nicht hinreichend. Es gibt nicht-reguläre Sprachen, die das Lemma trotzdem erfüllen. Regularität zeigt man anders (z.B. DFA/NFA/regulärer Ausdruck oder Myhill-Nerode).
Typ: Wahr/Falsch
Zuordnungen:
Erklärung: Reihenfolge: `p` gegeben, `w` wählst du (abhängig von `p`), der Gegner zerlegt, dann wählst du `i`. Du kontrollierst `w` und `i`, der Gegner `p` und die Zerlegung.
Typ: Zuordnung
Antwort: `\aⁿ bⁿ mid n ≥ 0\`
Erklärung: `\aⁿ bⁿ\` erfordert das Zählen und Vergleichen von `n`, was ein endlicher Automat nicht kann, der Beweis geht über das Pumping-Lemma. Die anderen drei Sprachen sind regulär (endlich viel zu merken: Endzeichen, Längen-Parität, oder gar nichts).
Klausurfragen mit Lösungen (6)
Antwort: Aus der Anzahl der Zustände eines DFA für `L` (Schubfachprinzip)
Erklärung: Hat ein DFA `p` Zustände und liest ein Wort der Länge `≥ p`, wiederholt sich ein Zustand (Schubfachprinzip). Die Schleife dazwischen ist der pumpbare Teil `y`. Daher ist `p` die Zustandszahl.
Lösungen pro Lücke:
Erklärung: Die drei Bedingungen: `|xy| ≤ p` (Hebel), `|y| ≥ 1` (`y` nicht leer), und `x yⁱ z ∈ L` für alle `i ≥ 0` (auch `i = 0`, also `y` weglassen).
Typ: Lückentext
Antwort: `i = 2` (oder `i = 0`)
Erklärung: Bei `i = 2` ist `x y² z = a^(p+k) b^p` mit `k ≥ 1`, also mehr `a` als `b`, nicht in `L`. Auch `i = 0` (also `a^(p-k) b^p`) bricht die Balance. `i = 1` ist das Originalwort und hilft nie.
Antwort: Weil das Lemma `x yⁱ z ∈ L` für ALLE `i` fordert, sodass ein Gegenbeispiel die Annahme widerlegt
Erklärung: Bedingung 3 verlangt `x yⁱ z ∈ L` für ALLE `i ≥ 0`. Ein einziges `i`, das herausführt, verletzt diese Allaussage und liefert den Widerspruch.
Antwort: Falsch
Erklärung: Falsch. Die Zerlegung wählt der Gegner. Dein Argument muss für JEDE zulässige Zerlegung gelten. Du sicherst das ab, indem du aus `|xy| ≤ p` folgerst, woraus `y` bestehen muss.
Typ: Wahr/Falsch
Antwort: `a^(p-k) b^p`, und es liegt NICHT in `L` (da `k ≥ 1`)
Erklärung: `x y⁰ z = ε · a^(p-k) b^p = a^(p-k) b^p`. Wegen `k ≥ 1` sind es weniger `a` als `b`, also nicht in `L`. Damit ist auch `i = 0` ein gültiger Widerspruch.
\aⁿ bⁿ\