Lexikon der Mathematik: Pumping-Lemma für kontextfreie Sprachen
Satz, mit dem die Nichtzugehörigkeit von Sprachen zur Klasse der kontextfreien Sprachen (Grammatik) gezeigt werden kann.
Zu jeder kontextfreien Sprache L existiert eine natürliche Zahl n so, daß jedes Wort w ∈ L, das länger als n ist, sich zerlegen läßt in w = u1v1u2v2u3, derart, daß die Länge von v1v2größer als 0 ist, und alle Wörter \({u}_{1}{v}_{1}^{i}{u}_{2}{v}_{2}^{i}{u}_{3}(i\ge 1)\)auch in L enthalten sind.
Analog zur Anwendung des Pumping-Lemmas für reguläre Sprachen kann z. B. gezeigt werden, daß die Sprache L = {an bn cn | n ≥ 1} nicht kontextfrei ist.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.