grammar - 为上下文相关语言抽取引理？

Question

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

抽引理只允许证明一种语言是上下文无关的吗？并且不区分上下文？

知道怎么做吗？

score 3 · Accepted Answer

Pumping lemmas 存在于常规、上下文无关、树相邻和多上下文无关的语言中。Johan Behrenfeld 的硕士论文中有一个很好的调查：

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

每个抽水引理都陈述了该类中语言的一个属性。它可以用来证明一种语言不在该类中，作为矛盾的证明。它不能用来证明一种语言属于该类。

score 2 · Accepted Answer

树邻接语言的“泵引引理”方法实际上在文献中到处都被称为“树邻接语言的泵引引理”。它可以证明一种语言不是树邻接的，因此不是温和的上下文敏感的。也许这就是你心目中的那个？

它是由 Vijay-Shanker 在他的博士论文中定义的，遗憾的是无法在线获得。尽管如此，通过搜索网络很容易找到它的工作原理。许多课程，例如蒂宾根大学的这门课程，都给出了很好的说明。

score -1 · Accepted Answer

有两个抽水引理。为正则语言抽取引理可以证明一种语言不是正则的。为上下文无关语言抽取引理可以证明一种语言不是上下文无关的，因此不是正则的。

没有其他抽水引理。要证明语言是上下文相关的，您可以首先使用 Pumping Lemma 证明它不是上下文无关的。然后，您必须提供实际生成给定语言的上下文相关语法。

3 回答 3