形式语言与自动机理论电子教案02

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第2章 文法,对任何语言,L,，有一个字母表，使得,L,*,。,L的具体组成结构是什么样的？,一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？,。,这些问题对有穷语言来说，比较容易解决。,这些问题对无穷语言来说，不太容易解决。,语言的有穷描述。,2024/9/21,1,第2章 文法,主要内容,文法的直观意义与形式定义，推导、文法产生的语言、句子、句型；,乔姆斯基,体系，左线性文法、右线性文法，文法的推导与归约；空语句。,重点,文法、推导、归约、模型的等价性证明。,难点,形式化的概念，文法的构造,。,2024/9/21,2,2.1 启示,文法的概念最早是由语言学家们在研究自然语言理解中完成形式化。,归纳如下句子的描述：,哈尔滨是美丽的城市。,北京是祖国的首都。,集合是数学的基础。,形式语言是很抽象的。,教育走在社会发展的前面。,中国进入,WTO,。,2024/9/21,3,2.1 启示,6,个句子的主体结构,=,哈尔滨，北京，集合，形式语言，教育，中国,=,是美丽的城市，是祖国的首都，是数学的基础，是很抽象的，走在社会发展的前面，进入,WTO,=,。,2024/9/21,4,2.1 启示,可以是,或者,。,=,北京、哈尔滨、形式语言、中国、教育、集合、,WTO,、美丽的城市、祖国的首都、数学的基础、社会发展的前面,。,=,是、走在、进入,。,=,很抽象的,。,把,取名为,。,2024/9/21,5,2.1 启示,2024/9/21,6,2.1 启示,表示成,形式,是,2024/9/21,7,2.1 启示,走在,进入,很抽象的,北京,哈尔滨,形式语言,2024/9/21,8,2.1 启示,中国,教育,集合,WTO,美丽的城市,祖国的首都,数学的基础,社会发展的前面,。,2024/9/21,9,2.1 启示,表示一个语言，需要,4,种东西,形如的,“,符号,”,它们表示相应语言结构中某个位置上可以出现的一些内容。每个,“,符号,”,对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种,“,符号,”,代表的是一个语法范畴。,所有的,“,规则,”,，都是为了说明,的结构而存在，相当于说，定义的就是,。,2024/9/21,10,2.1 启示,形如北京的,“,符号,”,它们是所定义语言的合法句子中将出现的,“,符号,”,。仅仅表示自身，称为终极符号,。,所有的,“,规则,”,都呈,的形式,在产生语言的句子中被使用，称这些,“,规则,”,为产生式。,2024/9/21,11,2.2 形式定义,文法(grammar),G=(V,，,T,，,P,，,S),V,为,变量,(variable),的非空有穷集。,A,V,，,A,叫做一个,语法变量,(syntactic Variable),，简称为变量，也可叫做,非终极符号,(nonterminal),。它表示一个,语法范畴,(syntactic Category),。所以，本文中有时候又称之为语法范畴,。,2024/9/21,12,2.2 形式定义,T,为,终极符,(terminal),的非空有穷集。,a,T,，,a,叫做终极符。由于,V,中变量表示语法范畴，,T,中的字符是语言的句子中出现的字符，所以，有,V,T=,。,SS,V,，为文法,G,的,开始符号,(start symbol)。,2024/9/21,13,2.2 形式定义,P,为,产生式,(production),的非空有穷集合。,P,中的元素均具有形式,，被称为产生式，读作：定义为。其中,(V,T),+,，且中至少有,V,中元素的一个出现。,(V,T),*,。称为产生式,的,左部,，称为产生式,的,右部,。产生式又叫做定义式或者语法规则。,2024/9/21,14,2.2 形式定义,例 2-1,以下四元组都是文法。,(A,，,0,，,1,，,A,01,，,A,0A1,，,A,1A0,，,A)。,(A,，,0,，,1,，,A,0,，,A,0A,，,A)。,(A,，,B,，,0,，,1,，,A,01,，,A,0A1,，,A,1A0,，,B,AB,，,B,0,，,A)。,(A,，,B,，,0,，,1,，,A,0,，,A,1,，,A,0A,，,A,1A ,，,A),。,2024/9/21,15,2.2 形式定义,(S,，,A,，,B,，,C,，,D,a,，,b,，,c,，,d,#,，,S,ABCD,，,S,abc#,，,A,aaA,，,AB,aabbB,，,BC,bbccC,，,cC,cccC,，,CD,ccd#,，,CD,d#,，,CD,#d,，,S)。,(S,a,，,b,，,S,00S,，,S,11S,，,S,00,，,S,11,，,S)。,2024/9/21,16,2.2 形式定义,约定,对一组有相同左部的产生式,1,，,2,，,，,n,可以简单地记为：,1,|,2,|,n,读作：定义为,1,，或者,2,，,，或者,n,。并且称它们为产生式。,1,，,2,，,，,n,称为,候选式(candidate)。,2024/9/21,17,2.2 形式定义, 使用符号,英文字母表较为前面的大写字母，如A，B，C，表示语法变量；,英文字母表较为前面的小写字母，如a，b，c，表示终极符号；,英文字母表较为后面的大写字母，如X，Y，Z，表示该符号是语法变量或者终极符号；,英文字母表较为后面的小写字母，如x，y，z，表示由终极符号组成的行；,希腊字母，,表示由语法变量和终极符号组成的行,2024/9/21,18,2.2 形式定义,例 2-3,四元组是否满足文法的要求。,(A,，,B,，,C,，,E,，,a,，,b,，,c,，,S,ABC|abc,，,D,e|a,，,FB,c,，,A,A,，,E,abc|,，,S),4种修改,(1) (A,，,B,，,C,，,E,，,S,，,D,，,F,，,a,，,b,，,c,，,e,，,S,ABC|abc,，,D,e|a,，,FB,c,，,A,A,，,E,abc|,，,S)。,(2) (A,，,B,，,C,，,E,，,S ,，,a,，,b,，,c,，,S,ABC|abc,，,A,A,，,E,abc|,，,S)。,(3) (A,，,B,，,C,，,E,，,a,，,b,，,c,，, A,A,，,E,abc|,，,A)。,(4) (A,，,B,，,C,，,E,，,a,，,b,，,c,，, A,A,，,E,abc|,，,E)。,2024/9/21,19,2.2 形式定义,推导(derivation),设,G=(V,，,T,，,P,，,S),是一个文法，如果,P,，,(V,T),*,，则称在,G,中直接推导出。,G,读作：在文法G中直接推导出。,“,直接推导,”,可以简称为,推导,(derivation)，也称推导为,派生。,2024/9/21,20,2.2 形式定义,归约,(reduction),G,称在文法,G,中直接归约成。在不特别强调归约的直接性时，,“,直接归约,”,可以简称为,归约。,2024/9/21,21,2.2 形式定义,1,推导与归约表达的意思的异同。,2,推导与归约和产生式不一样。所以，,G,和,所表达的意思不一样。,3,推导与归约是一一对应的。,4,推导与归约的作用。,2024/9/21,22,2.2 形式定义,G,、,G,+,、,G,*,当成,(V,T),*,上的二元关系。,(1),G,n,：表示在,G,中经过,n,步推导出；在,G,中经过,n,步归约成。即，存在,1,，,2,，,，,n-1,(V,T),*,使得,G,1,，,1,G,2,，,，,n-1,G,。,(2)当,n=0,时，有,=,。即,G,0,。,(3),G,+,：表示在,G,中经过至少,1,步推导出；在,G,中经过至少,1,步归约成。,2024/9/21,23,2.2 形式定义,(4),G,*,：表示在,G,中经过若干步推导 出；在,G,中经过若干步归约成。,分别用,、,+,、,*,、,n,代替,G,、,G,+,、,G,*,、,G,n,。,2024/9/21,24,2.2 形式定义,例 2-4,设,G=(A,，,a,，,A,a|aA,，,A),A,a,A,使用产生式,A,aA,aa,A,使用产生式,A,aA,aaa,A,使用产生式,A,aA,aaaa,A,使用产生式,A,aA,aa,A,使用产生式,A,aA,aaa,使用产生式,A,a,2024/9/21,25,2.2 形式定义,A,a,A,使用产生式,A,aA,aa,A,使用产生式,A,aA,aaa,A,使用产生式,A,aA,aaaa,A,使用产生式,A,aA,aa,A,使用产生式,A,aA,aaaA,使用产生式,A,aA,2024/9/21,26,2.2 形式定义,AAaaA,A,A,A,A,aaAaAA,使用产生式,A,aA,AaAaaAa,A,A,使用产生式,A,aA,A,aAaaAaaA,使用产生式,A,a,aaAaaAaa,A,使用产生式,A,a,aa,A,aaAaaa,使用产生式,A,a,aaa,A,aaAaaa,使用产生式,A,aA,aaaaaa,A,aaa,使用产生式,A,a,aaaaaaaaaa,使用产生式,A,a,2024/9/21,27,2.2 形式定义,例 2-5,设,G=(S,，,A,，,B,，,0,，,1,，,S,A|AB,，,A,0|0A,，,B,1|11,，,S),对于,n,1,，,A,n,0,n,首先连续,n-1,次使用产生式；,A,0A,， 最后使用产生式,A,0,；,A,n,0,n,A,连续,n,次使用产生式,A,0A,；,B,1,使用产生式,B,1,；,B,11,使用产生式,B,11。,2024/9/21,28,2.2 形式定义,语法范畴,A,代表的集合,L(A),=,0,，,00,，,000,，,0000,，,=0,n,|n,1,；,语法范畴,B,代表的集合,L(B),=,1,，,11,语法范畴S代表的集合,L(S)=L(A)L(A)L(B),=0，00，000，0000，0，00，000，0000，1，11,=0，00，000，0000，,01，001，0001，00001，,011,，,0011,，,00011,，,000011,，,2024/9/21,29,2.2 形式定义,例2-6,设,G=(A,，,0,，,1,，,A,01,，,A,0A1,，,A),，,A,n,0,n,A1,n,n,0,0,n,A1,n,0,n+1,A1,n+1,n,0,0,n,A1,n,0,n+1,1,n+1,n,0,0,n,A1,n,i,0,n+i,A1,n+i,n,0,，,i,0,0,n,A1,n,i,0,n+i,1,n+I,n,0,，,i,0,0,n,A1,n,*,0,m,A1,m,n,0,，,m,n,0,n,A1,n,+,0,m,1,m,n,0,，,m,n+1,0,n,A1,n,+,0,m,A1,m,n,0,，,m,n+1,0,n,A1,n,+,0,m,1,m,n,0,，,m,n+1,2024/9/21,30,2.2 形式定义,几点结论,对任意的,x,+,，我们要使语法范畴,D,代表的集合为,x,n,|n,0,，可用产生式组,D,|xD,来实现。,对任意的,x,，,y,+,，我们要使语法范畴,D,代表的集合为,x,n,y,n,|n,1,，可用产生式组,D,xy|xDy,来实现。,对任意的,x,，,y,+,，我们要使语法范畴,D,代表的集合为,x,n,y,n,|n,0,，可用产生式组,D,|xDy,来实现。,2024/9/21,31,2.2 形式定义,语言,(language),L(G)=w | w,T,*,且,S,*,w,句子,(sentence),w,L(G),，,w,称为,G,产生的一个,句子。,句型,(sentential form),G=(V,，,T,，,P,，,S),，对于,(V,T),*,，如果,S,*,，则称是,G,产生的一个,句型。,2024/9/21,32,2.2 形式定义,句子,w,是从,S,开始，在,G,中可以推导出来的终极符号行，它,不含,语法变量。,句型是从,S,开始，在,G,中可以推导出来的符号行，它,可能含有,语法变量。,例 2-7,给定文法,G=(S,，,A,，,B,，,C,，,D,a,，,b,，,c,，,d,#,，,S,ABCD|abc#,，,A,aaA,，,AB,aabbB,，,BC,bbccC,，,cC,cccC,，,CD,ccd#,，,CD,d#,，,CD,#d,，,S),2024/9/21,33,2.2 形式定义,S,A,BCD,使用产生式,S,ABCD,aa,A,BCD,使用产生式,A,aaA,aaaa,AB,CD,使用产生式,A,aaA,aaaaaabb,BC,D,使用产生式,AB,aabbB,aaaaaabbbbc,cC,D,使用产生式,BC,bbccC,aaaaaabbbbcccc,CD,使用产生式,cC,cccC,aaaaaabbbbcccc#d,使用产生式,CD,#d,2024/9/21,34,2.2 形式定义,S,A,BC,D,使用产生式,S,ABCD,A,bbccCD,使用产生式,BC,bbccC,aaAbbcc,CD,使用产生式,A,aaA,aa,A,bbccccd#,使用产生式,CD,ccd#,aaaa,A,bbccccd#,使用产生式,A,aaA,aaaaaa,A,bbccccd#,使用产生式,A,aaA,aaaaaaaaAbbccccd#,使用产生式,A,aaA,2024/9/21,35,2.2 形式定义,例 2-8,构造产生标识符的文法,G=(,，,，,，,，,0,，,1,，,，,9,，,A,，,B,，,C,，,，,Z,，,a,，,b,，,c,，,，,z,，,P, ),P= ,|,，,|,，,A|B|C|D|E|F|G|H|I|J|K|L|M|N|O，,P|Q|R|S|T|U|V|W|X|Y|Z,，,a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z,，,0|1|2|3|4|5|6|7|8|9 ,2024/9/21,36,2.2 形式定义,G,=(,，,，,，,0,，,1,，,2,，,，,9,，,A,，,B,，,C,，,，,Z,，,a,，,b,，,c,，,，,z,，,P, ),P,=,，,A|B|C|D|E|F|G|H|I|J|K|L|M|N,O|P|Q|R|S|T|U|V|W|X|Y|Z,，,a|b|c|d|e|f|g|h|i|j|k|l|m|n,o|p|q|r|s|t|u|v|w|x|y|z,，,2024/9/21,37,2.2 形式定义,|0|1|2|3|4|5,6|7|8|9 ，,A|B|C|D|E|F，,G|H|I|J|K,，,L|M|N|O|P|Q，,R|S|T|U|V,，,W|X|Y|Z|a|b，,c|d|e|f|g,，,h|i|j|k|l|m，,n|o|p|q|r,，,s|t|u|v|w|x,y|z ,2024/9/21,38,2.2 形式定义,3,3,23,23,n23,n23,8n23,8n23,d8n23,d8n23,id8n23,2024/9/21,39,2.2 形式定义,标识符,i,id,id8,id8n,id8n2,id823,id8n23,2024/9/21,40,2.2 形式定义,使用符号使文法更简洁,G=(,b,，,a,，,d,b|a|b|a|d, ),G=(L,，,b,，,a,，,d,，,L,b|a|Lb|La|Ld, L),G=(L,，,H,，,T,，, b,，,a,，,d ,，,L,HT,，,H,b|a,，,T,|bT|aT|dT, L),2024/9/21,41,2.3 文法的构造,例2-9,构造文法,G,，使,L(G)=0,，,1,，,00,，,11,将文法的开始符号定义为这,4,个句子。,G,1,=(S,，,0,，,1,，,S,0,，,S,1,，,S,00,，,S,11,，,S),先用变量,A,表示,0,，用变量,B,表示,1。,G,2,=(S,，,A,，,B,，,0,，,1,，,S,A,，,S,B,，,S,AA,，,S,BB,，,A,0,，,B,1,，,S),基于,G,2,，考虑,“,规范性,”,问题。,G,3,=(S,，,A,，,B,，,0,，,1,，,S,0,，,S,1,，,S,0A,，,S,1B,，,A,0,，,B,1,，,S),2024/9/21,42,2.3 文法的构造,可以在,V,、,T,中增加一些元素，以获得,“,不同的,”,文法。,G,4,=(S,，,A,，,B,，,C,，,0,，,1,，,2,，,S,A,，,S,B,，,S,AA,，,S,BB,，,A,0,，,B,1,，,S),G,5,=(S,，,A,，,B,，,C,，,0,，,1,，,2,，,S,A,，,S,B,，,S,AA,，,S,BB,，,A,0,，,B,1,，,CACS,21,，,C,11,，,C,2,，,S),L(G,1,)= L(G,2,)= L(G,3,)= L(G,4,)= L(G,5,),2024/9/21,43,2.3 文法的构造,等价(equivalence),设有两个文法,G,1,和,G,2,，如果,L(G,1,)= L(G,2,),，则称,G,1,与,G,2,等价。,约定,对一个文法，只列出该文法的所有产生式，且所列第一个产生式的左部是该文法的开始符号。,2024/9/21,44,2.3 文法的构造,G,1,：,S,0|1|00|11,G,2,：,S,A|B|AA|BB,，,A,0,，,B,1,G,3,：,S,0|1|0A|1B,，,A,0,，,B,1,G,4,：,S,A|B|AA|BB,，,A,0,，,B,1,G,5,：,S,A|B|BB,，,A,0,，,B,1,，,CACS,21,，,C,11,，,C,2,2024/9/21,45,2.3 文法的构造,例 2-10,L=0,n,|n,1,G,6,：,S,0|0S,L=0,n,|n,0,G,7,：,S,|0S,L=0,2n,1,3n,|n,0,G,8,：,S,|00S111,2024/9/21,46,2.3 文法的构造,例2-11,构造文法,G,9,，使,L(G,9,)=w|w,a,，,b,，,，,z,+,。,G,9,：,S,A|AS,A,a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z,用,S,A|AS,生成,A,n。,不可以用A,a|b|c|z表示。A,a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z,不可以用,A,a,8,表示,A,aaaaaaaa。,不能用,A,a,n,表示,A,可以产生任意多个,a。,2024/9/21,47,2.3 文法的构造,例2-12,构造文法,G,10,，使,L(G,10,)=ww,T,|w,0,，,1,，,2,，,3,+,。,文法,S,HE,H,0|1|2|3|0H|1H|2H|3H,E,0|1|2|3|E0|E1|E2|E3,难以生成L(G,10,)。,2024/9/21,48,2.3 文法的构造,ww,T,|w,0,，,1,，,2,，,3,+,的句子的特点,设,w=a,1,a,2,a,n,，从而有,w,T,= a,n,a,2,a,1,，,故,w w,T,= a,1,a,2,a,n,a,n,a,2,a,1,满足f(w w,T,，,i)=f(w w,T,，,|w w,T,|-i+1)。,递归地定义,L,对,a,0,，,1,，,2,，,3,，,aa,L,；,如果,x,L,，则对,a,0,，,1,，,2,，,3,，,axa,L,；,L,中不含不满足,(1),、,(2),任何其他的串。,2024/9/21,49,2.3 文法的构造,根据递归定义中的第一条，有如下产生式组：,S,00 | 11 | 22 | 33,再根据递归定义第二条，又可得到如下产生式组：,S,0S0 | 1S1 | 2S2 | 3S3,从而，,G,10,：,S,00 | 11 | 22 | 33 | 0S0 | 1S1 | 2S2 | 3S3,2024/9/21,50,2.3 文法的构造,例2-13,构造文法,G,12,，使,L(G,12,)=w|w,是我们习惯的十进制有理数,。,G,12,：,S,R | +R | -R,R,N | B,B,N.D,N,0 | AM,D,0 | MA,A,1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,M,| 0M | 1M | 2M | 3M | 4M | 5M | 6M | 7M | 8M | 9M,2024/9/21,51,2.3 文法的构造,例2-14,构造产生算术表达式的文法：,基础：常数是算术表达式，变量是算术表达式；,归纳：如果,E,1,、,E,2,是表达式，则,+E,1,、,-E,1,、,E,1,+E,2,、,E,1,-E,2,、,E,1,*E,2,、,E,1,/E,2,、,E,1,*E,2,、,Fun(E,1,),是算术表达式。其中,Fun,为函数名。,只有满足,(1),和,(2),的才是算术表达式。,G,13,：,E,id|c|+E|-E|E+E|E-E|E*E|E/E|E*E|Fun(E),2024/9/21,52,2.3 文法的构造,例2-15,构造产生语言,a,n,b,n,c,n,|n,1,的文法。,文法,G=(S,1,，,a,，,b,，,S,1,ab | aS,1,b,，,S,1,),产生的语言,a,n,b,n,| n,1,形式上看起来与语言,a,n,b,n,c,n,| n,1,比较接近。,G=(S,2,，,c,，,S,2,c | cS,2,，,S,2,),产生的语言是,c,n,|n1。,a,n,b,n,c,n,| n1a,n,b,n,| n1c,n,| n1,2024/9/21,53,2.3 文法的构造,文法,S,S,1,S,2,S,1,ab | aS,1,b,S,2,c | cS,2,不能产生语言,a,n,b,n,c,n,| n,1,而是产生语言,a,n,b,n,| n1c,n,| n1,2024/9/21,54,2.3 文法的构造,文法,G,：,S,abc | aSbc,产生的语言为：,a,n,(bc),n,| n,1,焦点：交换b和c的位置。,2024/9/21,55,2.3 文法的构造,G,14,：,S,aBC | aSBC,，,CB,BC,aB,ab,bB,bb,bC,bc,cC,cc,G,14,：,S,abc|aSBc,，,bB,bb,cB,Bc,2024/9/21,56,文法的乔姆斯基体系,文法,G=(V,，,T,，,P,，,S),G,叫做,0型文法(type 0 grammar),，也叫做,短语结构文法(phrase structure grammar, PSG)。,L(G),叫做,0型语言,。也可以叫做,短语结构语言(PSL)、递归可枚举集(recursively enumerable ，r.e. )。,2024/9/21,57,文法的乔姆斯基体系,G是0型文法。,如果对于,P,，均有,|,|,|,|,成立，则称,G,为,1型文法(type 1 grammar),，或,上下文有关文法(context sensitive grammar,CSG)。,L(G),叫做,1型语言(type 1 language),或者,上下文有关语言(context sensitive language ,CSL),。,2024/9/21,58,文法的乔姆斯基体系,G是1型文法,如果对于,P,，均有,|,|,|,|,，并且,V,成立，则称,G,为,2型文法(type 2 grammar),，或,上下文无关文法(context free grammar,CFG)。,L(G),叫做,2型语言(type 2 language),或者,上下文无关语言(context free language ,CFL)。,2024/9/21,59,文法的乔姆斯基体系,G是2型文法,如果对于,P,，,均具有形式,A,w,A,wB,其中,A,，,B,V,，,w,T,+,。,则称,G,为,3型文法(type 3 grammar),，也可称为,正则文法(regular grammar ,RG),或者正规文法。,L(G),叫做,3型语言(type 3 language),，也可称为,正则语言,或者,正规语言(regular language ,RL)。,2024/9/21,60,文法的乔姆斯基体系,如果一个文法,G,是,RG,，则它也是,CFG,、,CSG,和短语结构文法。反之不一定成立。,如果一个文法,G,是,CFG,，则它也是,CSG,和短语结构文法。反之不一定成立。,如果一个文法,G,是,CSG,，则它也是短语结构文法。反之不一定成立。,相应地：,RL,也是,CFL,、,CSL,和短语结构语言。反之不一定成立。,2024/9/21,61,文法的乔姆斯基体系,CFL,也是,CSL,和短语结构语言。反之不一定成立。,CSL,也是短语结构语言。反之不一定成立,当文法,G,是,CFG,时，,L(G),却可以是,RL,。,当文法,G,是,CSG,时，,L(G),可以是,RL,、,CSL,。, 当文法G是短语结构文法时，L(G)可以是RL、CSL和CSL。,2024/9/21,62,文法的乔姆斯基体系,定理 2-1,L,是,RL,的充要条件是存在一个文法，该文法产生语言,L,，并且它的产生式要么是形如：,A,a,的产生式，要么是形如,A,aB,的产生式。其中,A,、,B,为语法变量，,a,为终极符号。,证明,：,充分性：设有,G,，,L(G,)=L,，且,G,的产生式的形式满足定理要求。这种文法就是,RG,。所以，,G,产生的语言就是,RL,，故,L,是,RL。,2024/9/21,63,文法的乔姆斯基体系,必要性,构造：用,产生式组：,A,a,1,A,1,A,1,a,2,A,2,A,n-1,a,n,代替产生式,A,a,1,a,2,a,n,2024/9/21,64,文法的乔姆斯基体系,用,产生式组,A,a,1,A,1,A,1,a,2,A,2,A,n-1,a,n,B,代替产生式,A,a,1,a,2,a,n,B,2024/9/21,65,文法的乔姆斯基体系,证明,L(G,)=L(G),。,施归纳于推导的步数，证明一个更一般的结论：对于,A,V,，,A,G,+,x,A,G,+,x,。因为,S,V,，所以结论自然对,S,成立。,2024/9/21,66,文法的乔姆斯基体系,几点注意事项,我们是按照,RG,的一般定义来构造一个与之等价的文法的，这与读者以前熟悉的根据一个具体的对象构造另一个对象是不同的。在这里，可以使用的是非常一般的条件,一个一般模型。这也是这类问题的证明所要求的。而且在本书的后面，将会有更多这样的情况。,2024/9/21,67,文法的乔姆斯基体系,为了证明一个特殊的结论，可以通过证明一个更为一般的结论来完成。这从表面上好像是增加了我们要证明的内容，但实际上它会使我们能够更好地使用归纳假设，以便顺利地获得我们所需要的结论。,2024/9/21,68,文法的乔姆斯基体系,施归纳于推导的步数是证明本书中不少问题的较为有效的途径。有时我们还会对字符串的长度施归纳。,本证明的主要部分含两个方面，首先是构造，然后对构造的正确性进行证明。这种等价性证明的思路是非常重要的。,2024/9/21,69,文法的乔姆斯基体系,线性文法(liner grammar),设,G=(V,，,T,，,P,，,S),，如果对于,P,，,均具有如下形式：,A,w,A,wBx,其中,A,，,B,V,，,w,，,x,T,*,，则称,G,为,线性文法。,线性语言(liner language),L(G),叫做,线性语言,2024/9/21,70,文法的乔姆斯基体系,右线性文法(right liner grammar),设,G=(V,，,T,，,P,，,S),，如果对于,P,，,均具有如下形式：,A,w,A,wB,其中,A,，,B,V,，,w,，,x,T,*,，则称,G,为,线性文法。,右线性语言(right liner language),L(G),叫做右,线性语言。,2024/9/21,71,文法的乔姆斯基体系,左线性文法(left liner grammar),设,G=(V,，,T,，,P,，,S),，如果对于,P,，,均具有如下形式：,A,w,A,Bw,其中,A,，,B,V,，,w,，,x,T,*,，则称,G,为,线性文法。,左线性语言(left liner language),L(G),叫做右,线性语言。,2024/9/21,72,文法的乔姆斯基体系,定理2-2,L,是一个左线性语言的充要条件是存在文法,G,，,G,中的产生式要么是形如：,A,a,的产生式，要么是形如,A,Ba,的产生式，使得,L(G)=L,。其中,A,、,B,为语法变量，,a,为终极符号。,2024/9/21,73,文法的乔姆斯基体系,定理2-3,左线性文法与右线性文法等价。,按照定理,2-1,的证明经验，要想证明本定理，需要完成如下工作：,对任意右线性文法,G,，我们能够构造出对应的左线性文法,G,，使得,L(G,)=L(G),；,对任意左线性文法,G,，我们能够构造出对应的右线性文法,G,，使得,L(G,)=L(G)。,2024/9/21,74,文法的乔姆斯基体系,例 2-17,语言,0123456,的左线性文法和右线性文法的构造。,右线性文法,G,r,：,S,r,0A,r,A,r,1B,r,B,r,2C,r,C,r,3D,r,D,r,4E,r,E,r,5F,r,F,r,6,2024/9/21,75,文法的乔姆斯基体系,在文法,G,r,中的推导,S,r,0A,r,使用产生式,S,r,0A,r,01B,r,使用产生式,A,r,1B,r,012C,r,使用产生式,B,r,2C,r,0123D,r,使用产生式,C,r,3D,r,01234E,r,使用产生式,D,r,4E,r,012345F,r,使用产生式,E,r,5F,r,0123456,使用产生式,F,r,6,2024/9/21,76,文法的乔姆斯基体系,左线性文法,G,l,：,S,l,A,l,6,A,l,B,l,5,B,l,C,l,4,C,l,D,l,3,D,l,E,l,2,E,l,F,l,1,F,l,0,2024/9/21,77,文法的乔姆斯基体系,2024/9/21,78,文法的乔姆斯基体系,在文法,G,l,中的推导,S,l,A,l,6,使用产生式,S,l,A,l,6,B,l,56,使用产生式,A,l,B,l,5,C,l,456,使用产生式,B,l,C,l,4,D,l,3456,使用产生式,C,l,D,l,3,E,l,23456,使用产生式,D,l,E,l,2,F,l,1234456,使用产生式,E,l,F,l,1,0123456,使用产生式,F,l,0,2024/9/21,79,文法的乔姆斯基体系,被归约成文法,G,l,的开始符号,S,0,123456,F,l,1,234456,使用产生式,F,l,0,E,l,2,3456,使用产生式,E,l,F,l,1,D,l,3,456,使用产生式,D,l,E,l,2,C,l,4,56,使用产生式,C,l,D,l,3,B,l,5,6,使用产生式,B,l,C,l,4,A,l,6,使用产生式,A,l,B,l,5,S,l,使用产生式,S,l,A,l,6,2024/9/21,80,文法的乔姆斯基体系,2024/9/21,81,文法的乔姆斯基体系,定理 2-4,左线性文法的产生式与右线性文法的产生式混用所得到的文法不是,RG,。,证明：设有文法,G,15,：,S,0A,A,S1|1,不难看出，,L(G,15,)=0,n,1,n,|n,1,。我们构造不出,RG G,，使得,L(G)= L(G,15,)=0,n,1,n,|n,1,。因为,L(G,15,)=0,n,1,n,|n,1,不是,RL,。所以，,G,15,不是,RG,。有关该语言不是,RL,的证明我们将留到研究,RL,的性质时去完成。,2024/9/21,82,2.5 空语句,形如,A,的产生式叫做空产生式，也可叫做产生式。,在,RG,、,CFG,、,CSG,中，都不能含有空产生式。所以，任何,CSL,中都不含有空语句。从而,CFL,和,RL,中都不能含空语句。,空语句在一个语言中的存在并不影响该语言的有穷描述的存在性，甚至除了为生成空语句外，空产生式可以不被用于语言中其他任何句子的推导中。,2024/9/21,83,2.5 空语句,允许CSL、CFL、RL包含空语句后，还会给我们进行问题的处理提供一些方便。,允许在,RG,、,CFG,、,CSG,中含有空产生式,允许,CSL,、,CFL,、,RL,包含空语句。,2024/9/21,84,2.5 空语句,定理2-5,设,G=(V,，,T,，,P,，,S),为一文法，则存在与,G,同类型的文法,G,=(V,，,T,，,P,，,S,),，使得,L(G)=L(G,),，但,G,的开始符号,S,不出现在,G,的任何产生式的右部。,证明：,构造,当文法G=(V，T，P，S)的开始符号S不出现在P中的任何产生式的右部时，G就是所求,G,=(V,S,，,T,，,P,，,S,),P,=P,S,|S,P,2024/9/21,85,2.5 空语句,证明,L(G),L(G,),对任意的,x,L(G,),，由文法产生的语言的定义知，在,G,中存在如下推导：,S,使用产生式,S,*,x,使用,P,中的除,S,以外的其他产生式。,在推导,*,x,中使用的产生式都是,P,中的产生式。因此，推导,*,x,在,G,中仍然成立。,2024/9/21,86,2.5 空语句,由,P,的定义知，必有,S,P,所以，,S,使用,P,中的产生式,S,*,x,使用,P,中的产生式,故，,L(G,),L(G),2024/9/21,87,2.5 空语句,设G,中存在如下推导：,S,使用,P,中的产生式,S,*,x,使用,P,中的产生式,由P,=P,S,|S,P ,，知道,G,中，,S,使用产生式,S,*,x,使用,P,所包含的,P,中的其他产生式。,故，,L(G),L(G,)。,2024/9/21,88,2.5 空语句,设,G=(V,，,T,，,P,，,S),是一个文法，如果,S,不出现在,G,的任何产生式的右部，则：,如果,G,是,CSG,，则仍然称,G=(V,，,T,，,P,S,，,S),为,CSG,；,G,产生的语言仍然称为,CSL,。,如果,G,是,CFG,，则仍然称,G=(V,，,T,，,P,S,，,S),为,CFG,；,G,产生的语言仍然称为,CFL,。,如果,G,是,RG,，则仍然称,G=(V,，,T,，,P,S,，,S),为,RG,。,G,产生的语言仍然称为,RL。,2024/9/21,89,2.5 空语句,定理2-6,下列命题成立：,如果,L,是,CSL,，则,L,仍然是,CSL,。,如果,L,是,CFL,，则,L,仍然是,CFL,。,如果,L,是,RL,，则,L,仍然是,RL。,2024/9/21,90,2.5 空语句,证明：对第,1,个命题：设,L,是,CSL,，则存在一个,CSG G=(V,，,T,，,P,，,S),，使得,L(G)=L,。由定理,2-5-1,，我们不妨假设,S,不出现在,G,的任何产生式的右部。,取：,G,=(V,，,T,，,P,S,，,S),由于,S,不出现在,G,的任何产生式的右部，所以，,S,不可能出现在任何长度不为,0,的句子的推导中。,2024/9/21,91,2.5 空语句,易证：,L(G,)=L(G),。,由于,G,是,CSG,，所以，,L(G),是,CSL,。,同理可证第2和第3个命题。,2024/9/21,92,2.5 空语句,定理2-7,下列命题成立,如果,L,是,CSL,，则,L-,仍然是,CSL,。,如果,L,是,CFL,，则,L-,仍然是,CFL,。,如果,L,是,RL,，则,L-,仍然是,RL,。,2024/9/21,93,2.5 空语句,证明：对第,1,个命题：设,L,是,CSL,，则存在一个,CSG G=(V,，,T,，,P,，,S),，使得,L(G)=L,。如果,L,，则,L-,=L,，所以，,L-,是,CSL,。,如果,L,，由定理,2-5-1,，我们不妨假设,S,不出现在,G,的任何产生式的右部。取：,G,=(V,，,T,，,P-S,，,S),2024/9/21,94,2.5 空语句,由于,S,不出现在,G,的任何产生式的右部，所以，如果,L(G),中存在长度非,0,的句子，,S,不可能出现在它们的推导中。也就是说，将,S,从,G,中去掉后，不会影响,L(G),中任何长度非,0,的句子的推导。容易证明：,L(G,)=L(G)-,由于,G,是,CSG,，所以，,L(G)-,是,CSL,。,同理可证其他两个命题。,2024/9/21,95,2.5 空语句,对于任意文法,G=(V,，,T,，,P,，,S),，对于,G,中的其他变量,A,，出现形如,A,的产生式是不会改变文法产生的语言的类型的，而且这样一来，对我们进行文法的构造等工作还提供了很多方便。所以，我们约定：对于,G,中的任何变量,A,，在需要的时候，可以出现形如,A,的产生式。,2024/9/21,96,2.6 小结,本章讨论了语言的文法描述。首先介绍文法的基本定义和推导、归约、文法定义的语言、句子、句型、文法的等价等重要概念。讨论了如何根据语言的特点、通过用语法变量去表示适当的集合（语法范畴）的方法进行文法构造，并按照乔姆斯基体系，将文法划分成,PSG,、,CSG,、,CFG,、,RG,等,4,类。在这些文法中，线性文法是一类重要的文法。,2024/9/21,97,2.6 小结,文法,G=(V,，,T,，,P,，,S),。任意,A,V,表示集合,L(A)=w | w,T,*,且,A,*,w,。,推导与归约。文法中的推导是根据文法的产生式进行的。如果,P,，,(V,T),*,，则称在,G,中直接推导出：,G,；也称在文法,G,中直接