自然语言的计算复杂性研究(12)
http://www.newdu.com 2024/11/24 12:11:36 《外语教学与研究》2015年 冯志伟 参加讨论
此外,Culy(1985)研究过Bambara语词汇的形态,Bambara语是在马里及其邻国讲的一种叫做Mande语的西北方言,Culy的研究证明了 Bambara语的形态不能用上下文无关语法来描述｡ 这些研究说明,尽管自然语言的大部分现象可用上下文无关语法来描述,但是,很多学者认为,从总体上看,自然语言还不能算上下文无关的,自然语言的性质似乎介于上下文无关语言与上下文有关语言之间｡Chomsky(1980)指出,自然语言可能比上下文有关语言还要复杂,它可能是一种介于上下文无关语言与递归可枚举语言之间的语言,具有很高的计算复杂性｡ 尽管自然语言的计算复杂性很大,但是,我们仍然带着浓厚的兴趣来研究它,也许这正是研究自然语言的乐趣之所在(冯志伟 2012)｡ Chomsky(1956)首先提出这样的问题:有限状态语法或短语结构语法(也就是上下文无关语法)是不是可以充分地描述英语的句法?他提出,英语句法包含“一些例子是不容易用短语结构语法来解释的”,这促使他去研究句法转换的问题｡Chomsky根据形式语言{xxR:x∈{a,b}*}来证明正则语法的计算复杂性｡xR的意思是“x的镜像”,这种语言的每一个句子包含若干个a和若干个b组成的符号串,后面跟着这个符号串的“镜像”｡Chomsky证明了语言{xxR:x∈{a,b}*}不是正则语言｡Partee et al.(1990)把这种语言与正则语言aa*bbaa*求交,得到的语言是anb2an,然后再用抽吸引理来证明这种语言不是正则语言｡ Chomsky还说明,英语具有镜像的特性,据此,他认为,英语不是正则语言｡ Pullum(1991)明确地研究了关于自然语言的非上下文无关性质(non-context-free-ness)｡Pullum &Gazdar(1982)对证明自然语言的非上下文无关性质的早期工作进行了总结｡抽吸引理首先由Bar-Hillel et al.(1961)提出,他们也给出了关于正则语言或上下文无关语言的封闭性和可判定性的一些重要的证明｡ Yngve(1960)认为,如果人的剖析状态是有限的,那么,就可以据此来解释中心嵌套句子的计算复杂性;Church(1980)注意到Yngve的这个观点｡他证明了实现这种思想的有限状态剖析器也能够解释很多其他的语法现象和心理语言学现象｡Church的工作可以看成是自然语言处理研究向有限状态模型回归的开始,这成为了20世纪80年代和90年代自然语言处理研究的一个特点｡ 自然语言的计算复杂性还涉及到一些有趣的问题｡其中的一个问题是:自然语言处理是不是一个 NP完全问题(NP-complete problem)?所谓“NP完全问题”是指那些随着处理范围的增加,其计算量将呈指数性增长或失控地增长的问题｡这里的NP是“非确定多项式”(non-deterministic polynomial)缩写｡ (责任编辑：admin) |
- 上一篇：计算语言学的理论方法和研究取向
- 下一篇：自然语言处理技术与语言深度计算