grammar - 为上下文敏感语言抽引理？

Question

我在谷歌上搜索了上下文敏感的引理，它似乎只产生上下文无关语言的结果。

Pumping lemma 只能证明一种语言是上下文无关的吗？而不是上下文敏感？

知道怎么做吗？

Answer 1

抽水引理存在于常规的、上下文无关的、树邻接的和多上下文无关的语言中。 Johan Behrenfeld 的硕士论文中有一个很好的调查:

http://www.flov.gu.se/digitalAssets/1302/1302983_behrenfeldt-johan-alinguists.pdf

上下文相关语言没有抽水引理。事实上，这个类具有更大的生成能力，并且包括没有任何“抽水”属性的语言，例如{a^p | p 素数}。

每个抽引引理都说明了该类中的语言的一个属性。它可用于证明一种语言不属于该类，作为反证法。它不能用于证明一种语言在该类中。