Die Sprache endlicher Zustandsautomaten

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 Eine Sprache L ist definiert durch L = {x ∈ {a, b}* | x = akbk, k ∈ N} Siehe auch •