自然语言的计算复杂性研究(2)
http://www.newdu.com 2024/11/24 11:11:03 《外语教学与研究》2015年 冯志伟 参加讨论
一 关于自然语言的计算复杂性(computational complexity)的研究是语言学理论中一个重要而饶有趣味的问题,许国璋先生敏锐地关注到这个问题,说明了他的远见卓识｡ Chomsky(1956,1957,1959,1963)建立了形式语言理论(formal language theory)的完整系统,首先关注到自然语言的计算复杂性｡在形式语言理论中,Chomsky提出了不同于传统语法的形式语法(formal grammar)的定义,把形式语法理解为有限规则的集合,这些规则可以生成语言中的合格句子,并排除语言中的不合格句子｡ 形式语法的符号用G表示,语法G所生成的形式语言用L(G)表示｡形式语言是一种外延极为广泛的语言,它既可以指自然语言,也可以指各种用符号构成的语言(例如,计算机使用的程序设计语言)｡Chomsky把自然语言和各种符号语言放在一个统一的平面上进行研究｡ Chomsky把形式语法G定义为四元组:  其中,VN是非终极符号,不能处于生成过程的终点,VT是终极符号,只能处于生成过程的终点;VN与VT不相交,没有公共元素;S是VN中的初始符号;P是重写规则,其一般形式为:φ→ψ,其中的 φ和ψ都是符号串｡ 如果用符号#来表示符号串的界限,那么,可从初始符号串#S#开始,应用重写规则#S#→#φ1#,从#S#构成新的符号串#φ1#,再利用重写规则#φ1#→#φ2#,从#φ1#构成新的符号串#φ2#,……,一直到得出不能再继续重写的符号串#φn#为止,这样得出的终极符号串#φn#,就是形式语言L(G)中合格的句子｡ Chomsky根据重写规则的形式,把形式语法分为4类｡ 对于形式语法G={VN,VT,S,P},其重写规则为φ→ψ,并且要求φ≠Ø｡为了给语法进行分类,Chomsky对其重写规则加上一些限制:  (责任编辑：admin)
|
- 上一篇：计算语言学的理论方法和研究取向
- 下一篇：自然语言处理技术与语言深度计算