1

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

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

4

1 回答 1

0

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

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

所以没有捷径可走。

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

L → c
L → a L b b

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

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

于 2015-10-24T21:09:42.480 回答