形式语言与自动机-文法

引言

有如下句子:集合是数学的基础。该句子的主体结构为:<名词短语><动词短语><句号>

tim.png

表示成α®β形式:

<句子>®<名词短语><动词短语><句号>

<动词短语>®<动词><形容词短语>

<动词短语>®<动词><名词短语>

<动词>®

从上面可知,表示一种语言需要四种东西:类似<名词短语>的符号、句子、形如“集合”的符号、规则。

文法

    文法(grammar)  G=(VTPS) ,描述一种语言

  V——变量(variable)的非空有穷集。"AVA叫做一个语法变量(syntactic Variable),简称为变量,也可叫做非终极符号(nonterminal)。它表示一个语法范畴(syntactic Category)。所以,本文中有时候又称之为语法范畴

  T——终极符(terminal)的非空有穷集。"aTa叫做终极符。由于V中变量表示语法范畴,T中的字符是语言的句子中出现的字符,所以,有VT=Φ。

  S——SV,为文法G开始符号(start  symbol)

  P——产生式(production)的非空有穷集合。P中的元素均具有形式α®β,被称为产生式,读作:α定义为β。其中α∈(VT)+,且α中至少有V中元素的一个出现。β∈(VT)*。α称为产生式α®β的左部,β称为产生式α®β的右部。产生式又叫做定义式或者语法规则

       以下四元组都是文法。

({A}{01}{A®01A®0A1A®1A0}A)

({A}{01}{A®0A®0A}A)

({AB}{01}{A®01A®0A1A®1A0B®ABB®0}A)

({AB}{01}{A®0A®1A®0AA®1A }A)

    约定

(1)对一组有相同左部的产生式α®β1,α®β2 ,… ,α®βn,可以简单地记为:α®β1|β2|…|βn,读作:α定义为β1,或者β2,…,或者βn。并且称它们为α产生式。β1,β2,…,βn称为候选式(candidate)。

(2)使用符号

英文字母表较为前面的大写字母,如ABC,…表示语法变量

英文字母表较为前面的小写字母,如abc,…表示终极符号

英文字母表较为后面的大写字母,如XYZ,…表示该符号是语法变量或者终极符号;

英文字母表较为后面的小写字母,如xyz,…表示由终极符号组成的行

希腊字母α,β,γ…表示由语法变量和终极符号组成的行

 

    推导(derivation)

G=(VTPS)是一个文法,如果α®β∈P,γ,δ∈(VT)*,则称γαδ在G中直接推导出γβδ。

         γαδÞG γβδ

读作:γαδ在文法G中直接推导出γβδ。直接推导可以简称为推导(derivation)也称推导为派生  

    归约(reduction)

γαδÞγβδ

称γβδ在文法G中直接归约成γαδ。在不特别强调归约的直接性时,直接归约可以简称为归约

 

ÞGÞG+ÞG*当成(VT)*上的二元关系。

()αÞGn β:表示α在G中经过n步推导出β;β在G中经过n步归约成α。即,存在α1,α2,αn-1(VT)*使得αÞG α1,α1ÞG α2,αn-1ÞG β。 n=0时,有α=β。即αÞG0 α

()αÞG+ β:表示α在G中经过至少1步推导出β;β在G中经过至少1步归约成α。

()αÞG* β:表示α在G中经过若干步推导 出β;β在G中经过若干步归约成α。

  分别用ÞÞ+Þ*Þn代替ÞGÞG+ÞG*ÞGn

 

    几点结论

  对任意的x∈∑+,我们要使语法范畴D代表的集合为{xn|n0},可用产生式组{D®ε|xD}来实现。

  对任意的xy∈∑+,我们要使语法范畴D代表的集合为{xnyn|n1},可用产生式组{D®xy|xDy}来实现。

  对任意的xy∈∑+,我们要使语法范畴D代表的集合为{xnyn|n0},可用产生式组{D®ε|xDy}来实现。

 

    语言(language)  L(G)={w | wT*S Þ* w},T是为终极符(terminal)的非空有穷集的克林闭包。

    句子(sentence) "wL(G)w称为G产生的一个句子。句子w是从S开始,在G中可以推导出来的终极符号行,它不含语法变量。

    句型(sentential form) G=(VTPS),对于"α∈(VT)*,如果S Þ* α,则称α是G产生的一个句型。句型α是从S开始,在G中可以推导出来的符号行,它可能含有语法变量。

2-7

给定文法G=({SABCD},{abcd,#}{S®ABCD|abc#A®aaAAB®aabbBBC®bbccCcC®cccCCD®ccd#CD®d#CD®#d}S)

 

    等价(equivalence) 设有两个文法G1G2,如果L(G1)= L(G2),则称G1G2等价。

    约定 对一个文法,只列出该文法的所有产生式,且所列第一个产生式的左部是该文法的开始符号。 

 

文法的乔姆斯基体系

    文法G=(VTPS)

    G叫做0型文法(type 0 grammar),也叫做短语结构文法(phrase structure grammar, PSG)

    L(G)叫做0型语言。也可以叫做短语结构语言(PSL)递归可枚举集(recursively enumerable r.e. )

 

    如果对于"α®β∈P,均有|β||α|成立,则称G1型文法(type 1 grammar),或上下文有关文法(context sensitive grammar,CSG)

    L(G)叫做1型语言(type 1 language)或者上下文有关语言(context sensitive language ,CSL)

 

    如果对于"α®β∈P,均有|β||α|,并且α∈V成立,则称G2型文法(type 2 grammar),或上下文无关文法(context free grammar,CFG)

    L(G)叫做2型语言(type 2 language)或者上下文无关语言(context free language ,CFL)

 

    如果对于"α®β∈P,α®β均具有形式A®wA®wB,其中ABVwT+。则称G3型文法(type 3 grammar),也可称为正则文法(regular grammar ,RG)或者正规文法

    L(G)叫做3型语言(type 3 language),也可称为正则语言或者正规语言(regular language ,RL)

 

    如果一个文法GRG,则它也是CFGCSG和短语结构文法。反之不一定成立。

    如果一个文法GCFG,则它也是CSG和短语结构文法。反之不一定成立。

    如果一个文法GCSG,则它也是短语结构文法。反之不一定成立。

    相应地:

    RL也是CFLCSL和短语结构语言。反之不一定成立。

    CFL也是CSL和短语结构语言。反之不一定成立。

    CSL也是短语结构语言。反之不一定成立

    当文法GCFG时,L(G)却可以是RL

    当文法GCSG时,L(G)可以是RLCSL

    当文法G是短语结构文法时,L(G)可以是RLCSLCSL

 

定理:LRL的充要条件是存在一个文法,该文法产生语言L,并且它的产生式要么是形如:A®a的产生式,要么是形如A®aB的产生式。其中AB为语法变量,a为终极符号。

 

    线性文法(liner grammar)

  G=(VTPS),如果对于"α®β∈P,α®β均具有如下形式:

  A®w

  A®wBx

  其中ABVwxT*,则称G为线性文法。

    线性语言(liner language)

  L(G)叫做线性语言

    右线性文法(right liner grammar)

  G=(VTPS),如果对于"α®β∈P,α®β均具有如下形式:

  A®w

  A®wB

  其中ABVwxT*,则称G为线性文法。

    右线性语言(right liner language)

  L(G)叫做右线性语言。

    左线性文法(left liner grammar)

  G=(VTPS),如果对于"α®β∈P,α®β均具有如下形式:

  A®w

  A®Bw

  其中ABVwxT*,则称G为线性文法。

    左线性语言(left liner language)

  L(G)叫做右线性语言。

 

    定理:L是一个左线性语言的充要条件是存在文法GG中的产生式要么是形如:A®a的产生式,要么是形如A®Ba的产生式,使得L(G)=L。其中AB为语法变量,a为终极符号。

    定理:左线性文法与右线性文法等价。

    定理:左线性文法的产生式与右线性文法的产生式混用所得到的文法不是RG

 

空语句

    形如A®ε的产生式叫做空产生式,也可叫做ε产生式

    RGCFGCSG中,都不能含有空产生式。所以,任何CSL中都不含有空语句ε。从而CFLRL中都不能含空语句ε。

    空语句ε在一个语言中的存在并不影响该语言的有穷描述的存在性,甚至除了为生成空语句ε外,空产生式可以不被用于语言中其他任何句子的推导中。

    允许CSLCFLRL包含空语句ε后,还会给我们进行问题的处理提供一些方便。

    允许在RGCFGCSG中含有空产生式,允许CSLCFLRL包含空语句ε。

 

定理:设G=(VTPS)为一文法,则存在与G同类型的文法G=(V′,TP′,S),使得L(G)=L(G),但G′的开始符号S′不出现在G′的任何产生式的右部。

 

    G=(VTPS)是一个文法,如果S不出现在G的任何产生式的右部,则:

如果GCSG,则仍然称G=(VTP{S®ε}S)CSGG产生的语言仍然称为CSL

如果GCFG,则仍然称G=(VTP{S®ε}S)CFGG产生的语言仍然称为CFL

如果GRG,则仍然称G=(VTP{S®ε}S)RGG产生的语言仍然称为RL

 

定理:下列命题成立:

如果LCSL,则L{ε}仍然是CSL

如果LCFL,则L{ε}仍然是CFL

如果LRL,则L{ε}仍然是RL

 

定理:下列命题成立

如果LCSL,则L-{ε}仍然是CSL

如果LCFL,则L-{ε}仍然是CFL

如果LRL,则L-{ε}仍然是RL

 

    对于任意文法G=(VTPS),对于G中的其他变量A,出现形如A®ε的产生式是不会改变文法产生的语言的类型的,而且这样一来,对我们进行文法的构造等工作还提供了很多方便。所以,我们约定:对于G中的任何变量A,在需要的时候,可以出现形如A®ε的产生式。


首页 所有文章 机器人 计算机视觉 自然语言处理 机器学习 编程随笔 关于