语文网-语言文学网-读书-中国古典文学、文学评论、书评、读后感、世界名著、读书笔记、名言、文摘-新都网移动版

首页 > 学术理论 > 语言学 > 语言应用 >

自然语言的计算复杂性研究(2)


     
    关于自然语言的计算复杂性(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)