Informatik

Wozu dient das Pumping-Lemma für kontextfreie Sprachen?

Es liefert eine notwendige Eigenschaft kontextfreier Sprachen und wird meist genutzt, um zu zeigen, dass eine Sprache nicht kontextfrei ist.

Für lange Wörter ww gibt es eine Zerlegung w=uvxyzw=uvxyz, bei der vv und yy gemeinsam gepumpt werden können.