|
从S开始,用第一个重写规则(n-1)次,然后再用第二个重写规则一次,我们得到:  这样的语法可生成语言{anbn}｡ 由此可见,上下文无关语法的生成能力比正则语法强,Chomsky的上下文无关语法更能满足自然语言计算复杂性的要求｡从Chomsky层级可以知道,正则语法是包含在上下文无关语法之中的,那么,是不是存在着不是正则语言的上下文无关语言呢?这种语言的计算复杂性又如何呢?Chomsky(1963)针对这个问题给出了如下的回答｡ Chomsky指出,如果在上下文无关语法中,存在着某一非终极符号A,具有性质  ,这里,φ 和ψ 是非空符号串,推导式左边的A嵌入到推导式的右边,那么,这个语法就是自嵌入的(self-embedding)｡Chomsky证明了如果 G是非自嵌入的上下文无关语法,那么,L(G)就是正则语言｡他又证明了如果L(G)是上下文无关语言,那么,当且仅当文法G是具有自嵌入性质的上下文无关语法时,L(G)才不是正则语言｡这样,Chomsky便从理论上划清了真正的上下文无关语言与正则语言的界限｡ 前面讨论过的上下文无关语言{anbn},在语法的重写规则S→aSb中,规则左部的S自嵌入到规则右部aSb中去,这实际上就是  这样的推导式,具有自嵌入性质,因此,语言{anbn}不可能是正则语言,而是具有自嵌入性质的､真正的上下文无关语言,这样的语言不能满足抽吸引理｡ 三 现在我们就来研究自嵌入结构的问题｡为什么有的句子理解起来很困难呢?这种情况是否能告诉我们关于计算复杂性的某些信息呢? 很多因素都会造成句子理解的困难,如句子意思太复杂､句子歧义严重､句中使用太多罕用单词､句子书写质量太差,等等(冯志伟 2012)｡不过这些因素都是一些表面的问题,句子理解的另一类困难似乎与人的记忆局限性有关,与上下文无关语法的自嵌入特性存在着有趣的关系,这就牵涉到自然语言的计算复杂性问题了｡ Yngve(1960)指出英语中存在着中心嵌套结构(center-embedded structure)｡Partee et al.(1990)进一步研究了英语中的中心嵌套结构｡ (责任编辑：admin) |