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

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

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


    限制1要求语法的重写规则全都具有形式φ12→φ1ωφ2,这样的重写规则在上下文φ12中给出A→ω。显然,在这种情况下,ψ这个符号串的长度(即ψ中的符号数)至少等于或者大于φ这个符号串的长度(即φ中的符号数),如果用|ψ|和|φ|分别表示符号串ψ和φ的长度,则有|ψ|≥|φ|。由于在重写规则φ12→φ1ωφ2中,每当A出现于上下文φ12中的时候,可以用ω来替换A,因此,把加上了限制1的语法叫做上下文有关语法(context-sensitivegrammar)或1型语法(type 1grammar)。 
    限制2要求语法的重写规则全都具有形式A→ω,这时上下文φ12是空的,在运用重写规则时不依赖于单个的非终极符号A所出现的上下文,因此,把加上了限制2的语法叫做上下文无关语法(context-free grammar)或2型语法(type 2grammar)。 
    限制3要求语法的重写规则全都具有形式A→aQ或者A→a,其中,A和Q是非终极符号,a是终极符号,这种语法叫做正则语法(regular grammar)或3型语法(type 3grammar),又叫做有限状态语法(finite state grammar)。 
    没有上述限制的语法,叫做递归可枚举语法(recursive enumerable grammar)或0型语法(type 0 grammar)。 
        显而易见,每一个正则语法都是上下文无关的,每一个上下文无关语法都是上下文有关的,每一个上下文有关语法都是0型的。这样,我们可把由0型语法生成的语言叫0型语言(type 0 language),把由上下文有关语法、上下文无关语法、正则语法生成的语言分别叫做上下文有关语言、上下文无关语言、正则语言,也可分别叫做1型语言(type 1 language)、2型语言(type 2language)、3型语言(type 3language)。由于从限制1到限制3的限制条件是逐渐增加的,因此,不论对于语法或对于语言来说,都有。 
    任何的正则语法(3型语法)一定包含在上下文无关语法(2型语法)、上下文有关语法(1型语法)、递归可枚举语法(0型语法)中,任何的上下文无关语法(2型语法)一定包含在上下文有关语法(1型语法)、递归可枚举语法(0型语法)中,任何的上下文有关语法(1型语法)一定包含在递归可枚举语法(0型语法)中,这就是语法的 Chomsky层级(Chomsky hierarchy),如图1所示。 
    
    Chomsky认为,根据这样的形式语言理论,可以采用有限的规则来描述形式上是潜在地无限的句子,从而达到以简驭繁的目的。  (责任编辑:admin)