Der Beweis ist fertig. Ändern Sie das Wort x oder i und lassen Sie Lean prüfen.
Pumping-Lemma
Ist L regulär, so gibt es eine Zahl n ≥ 1 mit folgender Eigenschaft: Jedes Wort x ∈ L mit |x| ≥ n lässt sich zerlegen als x = u v w mit |u v| ≤ n und |v| ≥ 1, sodass u vi w ∈ L für alle i ≥ 0.
Als Spiel: Der Gegenspieler wählt n, Sie wählen x, der Gegenspieler zerlegt x, Sie wählen i. Können Sie beweisen, dass u vi w nicht in L liegt, haben Sie gewonnen.
Sie wählen (∃)Gegenspieler wählt (∀)Behauptung mit Begründungfolgt direkt
Ziel: Für jedes n ein x finden, sodass für jede Zerlegung ein i aus L hinausführt.