Pumping-Lemma (PL) liefert eine notwendige Bedingung für reguläre Sprachen.

Die Umkehrung des PL liefert die Möglichkeit, Sprachen auf Regularität zu überprüfen.

L ist eine reguläre Sprache über X.

Es gibt ein n ∈ N entsprechend PL

so, dass für alle x ∈ L mit

≥ n gilt: Es gibt Teilwörter u, v, w ∈ X* mit x =uvw, |uv| ≤ n (bzw. |vw| ≤ n),

≥ 1 und uviw ∈ L ∀ i ∈ N0. Beispiel 1 Eine Sprache L ist definiert durch L = {x ∈ {a, b}* | x = akbk, k ∈ N} Beispiel 2 L = {an b2n, | n ∈ N} 1. wähle n entsprechend PL 2. wähle Exemplaar x ∈ L: an b2n 3. Betrachte Zerlegungen in Teilweörter 4. Feststellung für alle diese Zerlegungen v in an 5. ⇒ uviw nur a's vervielfältigt ⇒ 2|uviw|a ≠ |uviw|a Siehe auch •