grammar - 乔姆斯基语言：如何识别它们？

Question

我对语言的识别有问题。例如，给定某种语言，如何根据乔姆斯基快速确定属于哪种类型？aⁿcb²ⁿ, n > 0

我的想法是确定生成它的语法，然后确定语言，但这是一个漫长的过程。我认为还有另一种方法可以通过肉眼识别它，而无需编写语法或自动机。有人能帮我吗？

Answer 1

不幸的是，在一般情况下，将任意语言与乔姆斯基层次结构的级别相关联是无法确定的。（见赖斯定理。）

当然，对给定的语法进行分类很容易，因为乔姆斯基层次结构是通过对语法本身的简单句法分析来定义的。然而，语言没有独特的语法。（例如）一种语言的类型 2（无上下文）语法的存在并不意味着同一语言不存在类型 3（常规）语法。

所以没有捷径可走。

但是，对于经验，有很多话要说。该语言是无上下文的（而不是常规的），就像所有类似形式的语言一样。语法证明了它是上下文无关的{ ancb2n | n > 0 }

L → c
L → a L b b

并且它不是正则的事实可以使用正则语言的抽引引理来证明。（链接的 Wikipedia 文章包含，作为使用引理的一个例子，一个类似语言的证明，应该很容易适应。）

另一方面，需要三个相等计数 ( ) 的语言不是上下文无关的（而是上下文相关的）。（这与 不一样，后者是上下文无关的。）{ ancnbn | n > 0 }{ ancn+mbm | n > 0 }