乔姆斯基语言：如何识别它们？
Chomsky languages: how to recognize them?
我的语言识别有问题。给定某种语言，例如ancb2n, n > 0，我如何确定根据乔姆斯基，很快属于什么类型？
我的想法是确定生成它的语法，然后确定语言，但这是一个漫长的过程。我认为还有另一种方法可以通过眼睛识别它，
无需编写语法或自动机。
有人可以帮我吗？
不幸的是，在一般情况下，将任意语言与乔姆斯基层次结构的级别相关联是无法确定的。 （参见 Rice's Theorem。）
当然，对给定的语法进行分类很容易，因为乔姆斯基层次结构是通过对语法本身的简单句法分析定义的。但是，语言没有独特的语法。一种语言存在（例如）Type 2（上下文无关）语法并不意味着同一种语言没有 Type 3（常规）语法。
所以没有捷径。
不过，经验还是有很多要说的。语言 { a<sup>n</sup>cb<sup>2n</sup> | n > 0 } 是上下文无关的（并且不是常规的），所有类似形式的语言也是如此。文法证明它是上下文无关的
L → c
L → a L b b
并且可以使用 pumping lemma for regular languages 来证明它不规则的事实。 （链接的维基百科文章包含作为引理使用示例的类似语言的证明，应该很容易适应。）
另一方面，一种语言需要三个相等的计数 ({ a<sup>n</sup>c<sup>n</sup>b<sup>n</sup> | n > 0 }) 不是上下文无关的（但上下文敏感）。 （这与 { a<sup>n</sup>c<sup>n+m</sup>b<sup>m</sup> 不同| n > 0 }，其中 是 上下文无关的。）
我的语言识别有问题。给定某种语言，例如ancb2n, n > 0，我如何确定根据乔姆斯基，很快属于什么类型？
我的想法是确定生成它的语法，然后确定语言，但这是一个漫长的过程。我认为还有另一种方法可以通过眼睛识别它， 无需编写语法或自动机。 有人可以帮我吗？
不幸的是，在一般情况下，将任意语言与乔姆斯基层次结构的级别相关联是无法确定的。 （参见 Rice's Theorem。）
当然，对给定的语法进行分类很容易，因为乔姆斯基层次结构是通过对语法本身的简单句法分析定义的。但是，语言没有独特的语法。一种语言存在（例如）Type 2（上下文无关）语法并不意味着同一种语言没有 Type 3（常规）语法。
所以没有捷径。
不过，经验还是有很多要说的。语言 { a<sup>n</sup>cb<sup>2n</sup> | n > 0 } 是上下文无关的（并且不是常规的），所有类似形式的语言也是如此。文法证明它是上下文无关的
L → c
L → a L b b
并且可以使用 pumping lemma for regular languages 来证明它不规则的事实。 （链接的维基百科文章包含作为引理使用示例的类似语言的证明，应该很容易适应。）
另一方面，一种语言需要三个相等的计数 ({ a<sup>n</sup>c<sup>n</sup>b<sup>n</sup> | n > 0 }) 不是上下文无关的（但上下文敏感）。 （这与 { a<sup>n</sup>c<sup>n+m</sup>b<sup>m</sup> 不同| n > 0 }，其中 是 上下文无关的。）