来自当知百科
跳转到: 导航搜索

  数理语言学用于生成语言的文法。形式文法是数目有限的规则的集合,这些规则可生成语言中的合格句子,并排除语言中的不合格句子。形式文法符号为 G,文法所生成的语言符号为L(G)。

  定义 美国语言学家N.乔姆斯基把形式文法 G定义为四个项目的组合:

   G=(□,□,S,P)其中,□是非终极符号,不能处于生成过程的终点;□是终极符号,能处于生成过程的终点;□与□不相交,没有公共元素; S是□中的初始符号; P是重写规则,其一般形式为:

   □→ψ这里,□和ψ都是符号串。

  如果用符号#来表示符号串中的界限,那么,可以从初始符号串#S#开始,应用重写规则#S#→#□#,从# S#构成新的符号串#□#,再利用重写规则#□#→#□#,从#□#构成新的符号串#□#,……一直到得出不能再继续重写的符号串#□#为止,这样得出的终极符号串#□#,显然就是语言L(G)中合格的句子。

  例如,在英语中,有如下的文法:

  G=(□,□,S,P)

  □={NP,VP,T,N,V}

  □ ={the,man,boy,ball,saw,hit,took,…}

  S=S

  P:S →NP⌒VP

   ①

  NP→ T⌒N

   ②

  VP→ V⌒NP

  ③

  T →the

   ④

  N →{man,boy,ball,…}

   ⑤

  V→{saw,hit,took,…}

   ⑥这里,初始符号S表示句子,NP表示名词短语,VP表示动词短语, T表示指示词, N表示名词,V表示动词。利用这些重写规则,可以从初始符号S开始,生成英语的句子“The man saw the ball”,“The man took the ball”,“The boy hit the ball”,等等。

  “The man saw the ball”的生成过程可写成如下形式,后面注明所用重写规则的号码:

   S

   NP⌒VP

   ①

   T⌒N⌒VP

   ②

   T⌒N⌒V⌒NP

  ③ the N⌒V⌒NP

   ④ the man V⌒NP

   ⑤ the man saw NP

   ⑥ the man saw T⌒N

  ② the man saw the N

   ④ the man saw the ball

  ⑤

  这样写出来的生成过程,叫做推导史。

  分类 乔姆斯基根据重写规则的形式,把形式文法分为 4类:

  ① O型文法:重写规则为□→ψ,并且要求□不是空符号串。

  ②上下文敏感文法:重写规则为□A□→□ω□。在上下文□→□中,单个的非终极符号 A被重写为符号串ω,所以,这种文法是上下文敏感的。

  ③上下文自由文法:重写规则为A→ω。当A重写为ω时,没有上下文的限制,所以,这种文法是上下文自由的。

  ④有限状态文法:重写规则为 A→aQ或A→a。其中,A和Q是非终极符号,a是终极符号,而A→a只不过是A→aQ当 Q为空符号时的一种特殊情况。如果把A和Q看成不同的状态,那么,由重写规则可知,由状态 A转入状态Q时,可生成一个终极终号a,因此,这种文法叫做有限状态文法。

  各种形式文法的关系 每一个有限状态文法上下文都是自由的,每一个上下文自由的文法上下文都是敏感的,每一个上下文敏感的文法都是 O型的。乔姆斯基把由O型文法生成的语言叫O型语言,把由上下文敏感文法、上下文自由文法、有限状态文法生成的语言分别叫做上下文敏感语言、上下文自由语言、有限状态语言。有限状态语言包含于上下文自由语言中,上下文自由语言包含于上下文敏感语言中,上下文敏感语言包含于 O型语言中。

  形式文法的理论是当代计算机科学的基础理论之一,在算法分析、编译技术、图像识别、人工智能等领域中得到广泛的应用。

  参考书目 N.Chomsky,Three models for the description oflanguage , 《 IRE Transaction of information Theory》.Vol.1,No.3,pp.113~124,1956.

个人工具
名字空间

变换
查看
操作
导航
工具箱