上下文无关语言的广义泵引理

Generalized Pumping Lemma for Context-Free Languages

摘要: 通常的关于上下文无关语言的泵引理，常被用来证明某些特殊的语言不是上下文无关的语言，但这种论证方法对有些非上下文无关语言不能适用。本文介绍的广义泵引理推广了通常的泵引理，并能解决通常的泵引理所不能解决的问题，它相比于Ｏｇｄｅｎ引理，未增加新的关于特指位置的概念，有些书上把泵引理中述及的条件，误认为是某语言成为上下文无关语言的充分条件，本文指出由此而引起的错误。

Abstract: A generalized pumping lemma is introduced.The generalized pumping lemmafurnishes eleganter technique than common pumping lemma for showing that certain lan-guages are non-context-free languages.By comparison with Ogden lemma,the generalizedpumping lemma does not add new concept about distinguished positions.