计算理论课后习题答案省公共课一等奖全国赛课获奖课件.pptx

《计算理论课后习题答案省公共课一等奖全国赛课获奖课件.pptx》由会员分享，可在线阅读，更多相关《计算理论课后习题答案省公共课一等奖全国赛课获奖课件.pptx（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 习题1给定文法给定文法G=(S,B,C,D,E,0,1,P,S)，其中其中P：SABC，AB0AD，AB1AE，AB，D00D，D11D，E00E，E11E，C，DCB0C，ECB1C，0BB0，1BB1试写出句子试写出句子01100110派生过程。派生过程。解解：SABC0ADC0AB0C01AE0C01A0EC01A0B1C01AB01C011AE01C011A0E1C011A01EC011A01B1C011A0B11C011AB011C0110AD011C0110A0D11C0110A01D1C0110A011DC0110A011B0C0110A01B10C0110A0B110C

2、0110AB0110C01100110C01100110第1页2设计以下各文法设计以下各文法G，使得它们分别是：使得它们分别是：（1）G是个上下文无关文法，且是个上下文无关文法，且 L(G)=aibj ck i,j,k1。（2）G是个正规文法，且是个正规文法，且 L(G)=aibj ck i,j,k1。（3）G是个上下文无关文法，且是个上下文无关文法，且 L(G)=wwRw0,1+。其中其中wR是是w逆转，例逆转，例如如w=001,则则wR=100.解解：设计一个文法：设计一个文法G要验证要验证：凡是符合要求句子凡是符合要求句子G都能产生出来；都能产生出来；G产生出来全部句子都是符合要求。产生

3、出来全部句子都是符合要求。(1)G=(S,A,B,C,a,b,c,P,S)P:SABC,AaA|a,BbB|b,CcC|c第2页(2)G=(S,A,B,C,a,b,c,P,S)P:SaA,AaA|bB,BbB|cC,CcC|(3)G=(S,0,1,P,S)P:S0S0|1S1|00|11 第3页第二章 习题1设计一个有限自动机设计一个有限自动机(FA)M，使得使得T(M)中每个句中每个句子子w同时满足下面三个条件：同时满足下面三个条件：1)wa,b,*；2)|w|是是3整数倍；整数倍；3)w以以a开头，以开头，以b结尾。结尾。解：解：q0q1q3q2q4aa,ba,ba,bb第4页2设计二个设

4、计二个FA M1和和M2，分别满足分别满足 T(M1)=02i i是自然数是自然数 T(M2)=02i+1 i=0,1,2,3,4,解：解：M1：q0q1q3000q1q000q0q100M2：第5页3.给定给定NFA M1=(p,q,r,s,0,1,p,s)，以下表所表示。以下表所表示。结构一个结构一个DFA M2，使得使得T(M1)=T(M2)。解解：令：令 M2=(K,q0,F),其中其中 K 2K，K中元素是由中元素是由K子集子集q1,q2,qi组成，不过要把子集组成，不过要把子集q1,q2,qi作为一个状态对待，作为一个状态对待，所以把此子集写成所以把此子集写成q1,q2,qi。q0

5、=q0,F=q1,q2,qi|q1,q2,qiK且且q1,q2,qiF：KK，对对 q1,q2,qiK,a，有有 (q1,q2,qi,a)=p1,p2,pj当且仅当当且仅当 (q1,q2,qi,a)=p1,p2,pj 0 1 p p,q p q r r r s s s s第6页q0=p,K和和F以后确定。以后确定。：0 1 p p,q p q r r r s s s sp01p,qpp,qp,q,rp,rp,rp,q,spp,q,rp,q,r,sp,rp,q,sp,q,r,sp,r,sp,r,sp,q,sp,sp,sp,q,sp,sp,q,r,sp,q,r,sp,r,sK=p,p,q,p,r,

6、p,s,p,q,r,p,q,s,p,r,s,p,q,r,sF=p,s,p,q,s,p,r,s,p,q,r,spp,qp,rp,q,rp,q,s p,r,s p,sp,q,r,s0100000010111111第7页4.将下面将下面-NFA M等价变换成等价变换成NFA M。abcdef1010：对任何：对任何qK,任何任何a,(q,a)=(q,a)。解解：M=(K,q0,F)，q0是是M开始状态，其中开始状态，其中公式公式(1)：对于：对于 qK,(q,)=-CLOSURE(q)公式公式(2)：对于对于 qK,w*,a,(q,wa)=-CLOSURE(q,w),a)第8页因为因为f CLOSU

7、RE(a)=a,b,所以所以F=F=f：qK,任何任何a,abcdef1010(q,a)=(q,a)。在计算在计算 (q,a)时，要将时，要将a了解成了解成a路径路径！比如比如(a,0)=(a,0)=c,e,d,b。:01abcdefc,e,d,bd,bd,bff,d,bfd,bff,d,b第9页5化简正规表示式化简正规表示式 a(+aa)*(+a)b+b+(ab*+b)*。解解：上式上式a(aa)*(+a)b+b其中其中(aa)*(+a)代表集合：代表集合：,aa,aaaa,aaaaaa,a=,aa,aaaa,aaaaaa,a,aaa,aaaaa,=,a,aa,aaa,aaaa,aaaaa,

8、aaaaaa,=a*于是上式于是上式aa*b+b=a+b+b=(a+)b=a*b第10页6结构一个结构一个FA M，使得使得T(M)正规表示式为正规表示式为01+(0+1)*1)*。解解：1.分解表示式，找出基本单元：分解表示式，找出基本单元：0,1,01,1。设计接收。设计接收这些基本单元自动机以下：这些基本单元自动机以下：q1q20q3q41q7q81q5q60q9q101第11页2.组装：组装：（按照优先权从高到低）（按照优先权从高到低）01+(0+1)*1)*q7q81q5q60q9q171q0q15q10q16q12q2q10q3q41q14q13q11第12页7给定给定FA M以下

9、列图所表示，求它所接收语言以下列图所表示，求它所接收语言T(M)正正规表示式。规表示式。解解：q2q10011第13页第14页8.将下面有限自动机简化将下面有限自动机简化(要求有简化过程要求有简化过程)。解解：一一.定义定义K上等价关系上等价关系 给定给定DFA M=(K,q0,F)，p,qK,p q 对对 x*,有有 (p,x)F(q,x)F假如假如p q 也称也称p与与q是不可区分。是不可区分。二二.商集商集K/三三 逆关系逆关系 p q x(x*(p,x)F(q,x)F)x(x*(p,x)F(q,x)F)(p,x)F(q,x)F)x(x*，使得使得(p,x)与与(q,x)恰有一个在恰有一

10、个在F中中)假如假如p q,称称p与与q是可区分是可区分。判断。判断p q是比较轻易。是比较轻易。abcfed00,10 00101111第15页4 4判断可区分状态正确算法判断可区分状态正确算法引理引理2-1 设设M=(K,q0,F)是是DFA，则状态对则状态对(p,q)是可区分是可区分(即即p q)，当且仅当在下面算法中当且仅当在下面算法中(p,q)格写上格写上。begin 1for pF,qK-F,do 给给(p,q)格写格写；2for FF或或(K-F)(K-F)中每个状态对中每个状态对(p,q)(pq)，do3if a，使得格使得格(p,a),(q,a)内已经写上内已经写上，then

11、 begin4 给给(p,q)格写格写；5 假如刚才写上假如刚才写上格内有先前写入状态对，此状态对格内有先前写入状态对，此状态对 格同时也写入格同时也写入。重复执行。重复执行5,直到写入直到写入格内没格内没 有先前写入状态对为止；有先前写入状态对为止；end else/*格格(p,a),(q,a)内无内无 */6for 每个每个a,do 7把把(p,q)写入格写入格(p,a),(q,a)内，除非内，除非(p,a)=(q,a)。end第16页执行此算法结果用一个表表示，实际上，执行此算执行此算法结果用一个表表示，实际上，执行此算法过程就是向这个表内写入法过程就是向这个表内写入“”“”过程。过程。

12、a b c d ebcdef (b,d)abcfed00,10 00101111 (a,b):ab0 1be?(a,c):ac0 1ba(a,d):ad0 1bfbd0 1cd0 1ef0 1bc0 1(b,c):(b,d):(c,d):(e,f):eaeffeafddfe得：得：b d,e f,a a,c c c第17页于是于是 K/a,b,d,c,e,f，五结构简化有限自动机五结构简化有限自动机定理定理2-5.1 给定给定DFA M(K,q0,F)，可依据引理可依据引理2-1中中算法结构出除去不可达状态含有更少状态算法结构出除去不可达状态含有更少状态DFA M，使得使得T(M)=T(M)。

13、证实：证实：先对先对M用引理用引理2-1中算法求出中算法求出K/。再结构再结构M：M=(K,q0,F)，其中其中 K=q|qK/且在且在M中中q是从是从q0 可达状态可达状态 F=q|qF ：对任何对任何qK，任何任何a,(q,a)=(q,a)第18页K/a,b,d,c,e,f=a,b,c,e，(b=b,d,e=e,f)K=a,b,c,e F=eM=(K,a,F)=(a,b,c,e,0,1,a,e)(q,a)=(q,a)abcfed00,10 00101111:0 1abcebcbeaaeeab0c1e0,10,1 01第19页9给定给定DFA M如图所表示。求一个左线性文法如图所表示。求一个

14、左线性文法G，使得使得L(G)=T(M)。解解：有两种方法。：有两种方法。方法方法11.先将先将M逆转成逆转成M：BAC10100,1BAC10100,1S2.依据依据M结构右线性文结构右线性文法法G：SA|C|A0BB0A|0C|1C|0C1A|1B|13.将将G逆转成左线性逆转成左线性文法文法G:SA|C|AB0BA0|C0|C1|0CA1|B1|1P=qap|(q,a)=pqa|(q,a)F。第20页方法方法21.先依据先依据M结构右线性文法结构右线性文法G：A0B|1C|1 (其中其中A是开始变元是开始变元)B0A|1C|0|1 C0B|1B2.再将再将G直接变成左线性文法直接变成左线

15、性文法G:依据定理：依据定理：(1)S,当且仅当当且仅当 SP；(2)Ai,当且仅当当且仅当 SAiP；(3)AiAj,当且仅当当且仅当 AjAiP；(4)SAj,当且仅当当且仅当 AjP。(1)由由A1 得得:A1 (2)由由A0B 得得:B0 由由A1C 得得:C1(3)由由B0A 得得:A B0 由由B1C 得得:CB1 由由C0B 得得:BC0 由由C1B 得得:BC1(4)由由 B0 得得:AB0 由由B1 得得:AB1BAC10100,1第21页方法方法21.先依据先依据M结构右线性文法结构右线性文法G：A0B|1C|1|(其中其中A是开始变元是开始变元)B0A|1C|0|1 C0

16、B|1B因开始变元因开始变元A出现在产生式右侧，故引入新开始变元出现在产生式右侧，故引入新开始变元S，SA(其中其中S是开始变元是开始变元)A0B|1C|1|B0A|1C|0|1 C0B|1BBAC10100,1第22页2.再将再将G直接变成左线性文法直接变成左线性文法G:依据定理：依据定理：(1)S,当且仅当当且仅当 SP；(2)Ai,当且仅当当且仅当 SAiP；(3)AiAj,当且仅当当且仅当 AjAiP；(4)SAj,当且仅当当且仅当 AjP。(2)SA 得得:A(3)由由A0B 得得:BA0 由由A1C 得得:CA1 由由B0A 得得:A B0 由由B1C 得得:CB1 由由C0B 得

17、得:BC0 由由C1B 得得:BC1(4)由由A1 得得:SA1 由由A 得得:SA 由由 B0 得得:SB0 由由B1 得得:SB1第23页整理得左线性文法整理得左线性文法G:SA1|B0|B1|A A B0|BA0|C0|C1 CA1|B1表面上看与方法表面上看与方法1得结果略有些不一样得结果略有些不一样 SA|C|AB0 BA0|C0|C1|0 CA1|B1|1第24页10首先结构一个右线性文法首先结构一个右线性文法G，使得使得 L(G)=ai bj|i,j0ck|k0再结构一个有限自动机再结构一个有限自动机M，使得使得T(M)=L(G)。解解：令：令G=(S,A,B,C,a,b,c,P

18、,S)P:SA|C|AaA|B|BbB|b|CcC|c|令令M(S,A,B,C,a,b,c,S,E)SBcAaCb第25页11给定右线性文法给定右线性文法G=(S,B,C,D,0,1,P,S)，其中其中P：SB C，B0B 1B 011,试求一个试求一个FA M，使得使得 T(M)=L(G)。C0D 1C,D0C 1D解解：此题与第：此题与第10题类似。题类似。要将要将G变成简单右线性文法，唯一要处理产生式是变成简单右线性文法，唯一要处理产生式是 B011，将它变成：将它变成：B0F,F1G,G 1第26页12.证实证实Lai|i是个素数是个素数不是正规集。不是正规集。证实证实:(1)假设假设

19、L是正规集。是正规集。(2)令令n是是L满足正规集泵作用引理常数。满足正规集泵作用引理常数。(3)取取zam，mn 且且m是个素数。是个素数。|z|=mn,依据正规集依据正规集泵作用引理，可将泵作用引理，可将z写成写成 z=uvw 形式，其中形式，其中|uv|n,|v|1,且对任何且对任何i0 有有 uviwL。(4)令令u=an1,v=an2,w=an3,于是于是|uv|=n1+n2n,|v|=n21,n1+n2+n3=m,z=uvw=an1+n2+n3=a m,uviw=an1+in2+n3=a(n1+n2+n3)+(i-1)n2=am+(i-1)n2取取i=m+1,则则 uvm+1w=a

20、m+(m+1-1)n2=am+mn2=am(1+n2)因为因为n21，所以所以1+n2 2,而而m2,所以所以m(1+n2)不是素不是素数，故数，故 uvm+1w L，产生矛盾。所以产生矛盾。所以L不是正规集。不是正规集。第27页第三章 习题1给定给定CFG G=(S,A,B,C,a,b,c,P,S)，其中，其中，P：SA|B,AAb|bS|C|b,BAB|Ba,CAS b,去掉去掉G中无用符号和单一生成式。中无用符号和单一生成式。解解：定义定义：给定：给定CFG G=(,S)，假如在假如在G中存中存在派生在派生S*X*w，其中其中w*，X，则称符号则称符号X是有用，不然是有用，不然X是无用。

21、是无用。利用两个引理，去掉无用符号。利用两个引理，去掉无用符号。注意：注意：一定是先应用引理一定是先应用引理3-2.1,后应用引理后应用引理3-3.2!第28页引理引理3-2.1 给定给定CFG G=(,S)，且且L(G)，可可以找到一个与以找到一个与G等价等价CFG G=(,S)，使得使得每个每个A，都有，都有w*，且在，且在G中有中有A*w。证实证实：1）求）求算法算法：begin OLD:=NEW:=A|AwP 且且w*While OLDNEW do begin OLD:=NEW NEW:=OLDA|AP,且且(OLD)*end :=NEW,end第29页引理引理3-2.2 给定给定CF

22、G G=(,S)，能够找到一个能够找到一个与与G等价等价CFG G，G=(,S)，使得每使得每个个X()，都有，都有,()*，且在，且在G中有派中有派生生S*X。证实证实：1执行下面迭代算法求执行下面迭代算法求和和。1）置初值：置初值：:=S，:=;2）假如假如A，在，在P中又有产生式中又有产生式A1|2|m，则能够将则能够将1,2,m中全部变元加到中全部变元加到中，将中，将1,2,m中全部终极符加到中中全部终极符加到中中。重复中。重复2)。3）若没有新符号可加入到若没有新符号可加入到、中，算法停中，算法停止。止。最终得到最终得到、。第30页P：SA|B,AAb|bS|C|b,BAB|Ba,C

23、AS b,对对G应用引理应用引理3-2.1，执行上述算法，得到结果以下表所，执行上述算法，得到结果以下表所示。示。循环次数i 初值 1 2 3OLDNEWA,C,SA,C A,CA,C,SA,C,S最终得最终得GCFG G=(S,A,C,a,b,c,P,S),其中其中 P：SA,AAb|bS|C|b,CAS|b实际上，只去掉了不能推出终极符串变元实际上，只去掉了不能推出终极符串变元B。再对再对G应用引理应用引理3-2.2：第31页P：SA,AAb|bS|C|b,CAS|b再对再对G用引理用引理3-2.2处理，执行算法结果以下表所表示：处理，执行算法结果以下表所表示：循环次数i 初值 1 2 3

24、 S S,A S,A,C T b 最终得最终得G=(S,A,C,b,P,S)P:SA,AAb|bS|C|b,CAS|b实际上只去掉了无用符号实际上只去掉了无用符号a和和c。第32页下面对下面对G去掉单一产生式去掉单一产生式:对任何对任何A,B，假如有，假如有A*B，且且B1|2|n是是 P中中B全部非单一产生式，则把全部非单一产生式，则把全部全部A1|2|n 加加到到P 中。中。P:SA,AAb|bS|C|b,CAS|b下面去掉单一产生式下面去掉单一产生式SA,AC,得得P：SAb|bS|C|b,AAb|bS|AS|b,CAS|b再去掉再去掉SC,得得 SAb|bS|AS|b,AAb|bS|A

25、S|b,CAS|b不过，能够看出不过，能够看出C是无用符号，所以是无用符号，所以CAS|b也被去掉。也被去掉。最终得：最终得：G=(S,A,b,P,S)P:SAb|bS|AS|b,AAb|bS|AS|b,第33页2给定给定CFG G=(S,A,B,C,a,b,P,S)，其中，其中，P：SABC,ABB|,BCC|a,CAA|b,去掉去掉G中中生成式。生成式。解解：首先首先求出可为零变元，即能够推出求出可为零变元，即能够推出变元。变元。显然有显然有A、C、B和和S。假如假如AX1X2XnP，则将全部形如则将全部形如A12n产生式都加到产生式都加到P中，其中中，其中 假如假如Xi不是可为零，则不是

26、可为零，则iXi。假如假如Xi是可为零，则是可为零，则iXi或者或者i。不过，不过，假如全部假如全部Xi(i=1,2,n)都是可为零，则不可全部都是可为零，则不可全部i。于是最终得：于是最终得：SABC|BC|AC|AB|C|B|A,ABB|B,BCC|C|a,CAA|A|b,第34页3给定给定CFG G=(S,A,0,1,P,S)，其中，其中，P：SAA 0,ASS 1,将将G写成写成GNF形式。形式。解解：此时：此时G已经具备已经具备CNF形式。形式。(ABC,Da)(1)变元重新命名：令变元重新命名：令A1=S,A2=A,P:A1A2A2|0 ,A2A1A1|1,(2)处理处理A2 A1

27、A1|1,变成：变成：A2A2A2A1|0A1|1,(3)处理左递归处理左递归A2A2A2A1|0A1|1,变成：变成：A20A1|1|0A1Z2|1Z2,Z2 A2A1|A2A1 Z2,(4)处理处理A1A2A2|0，得得 A1 0A1A2|1A2|0A1Z2A2|1Z2A2|0 (5)处理处理Z2 A2A1|A2A1 Z2,分别得：分别得：Z2 0A1A1|1A1|0A1Z2A1|1Z2A1 Z2 0A1A1Z2|1A1Z2|0A1Z2A1Z2|1Z2A1Z2第35页最终得最终得G=(A1,A2,Z2,0,1,P,A1)P:A1 0A1A2|1A2|0A1Z2A2|1Z2A2|0 A20A

28、1|1|0A1Z2|1Z2,Z2 0A1A1|1A1|0A1Z2A1|1Z2A1 Z2 0A1A1Z2|1A1Z2|0A1Z2A1Z2|1Z2A1Z2 第36页4结构一个结构一个PDA M，使得使得T(M)=w|wa,b*w 中中a,b个数相等个数相等。解解：设计思想：设计思想：有两个状态有两个状态q1和和q2：q1是开始状态，是开始状态，q2 是终止状态。是终止状态。栈内符号：栈内符号：A，B，R(R是开始时栈内符号是开始时栈内符号)。开始时开始时：读读a，向栈压入，向栈压入A；读读b，向栈压入向栈压入B。之后之后：当：当读读a时：假如栈顶是时：假如栈顶是A，再向栈压入一个再向栈压入一个A；

29、假如栈顶是假如栈顶是B，则则B退栈。退栈。当当读读b时：假如栈顶是时：假如栈顶是B，再向栈压入一个再向栈压入一个B；假如栈顶是假如栈顶是A，则则A退栈。退栈。假如假如w中中a,b个数相等，则个数相等，则M读完读完w后后，栈顶应该是，栈顶应该是R，此时此时M进入终止状态进入终止状态q2。第37页令令M=(q1,q2,a,b,A,B,R,q1,R,q2)(q1,a,R)=(q1,AR)(q1,b,R)=(q1,BR)(q1,a,A)=(q1,AA)(q1,a,B)=(q1,)(q1,b,A)=(q1,)(q1,b,B)=(q1,BB)(q1,R)=(q2,)如如w=bbabaa 时，时，M识别识别

30、w过程：过程：表示表示ID间改变。间改变。(q1,bbabaa,R)(q1,babaa,BR)(q1,abaa,BBR)(q1,baa,BR)(q1,aa,BBR)(q1,a,BR)(q1,R)(q2,)再如再如wabbab，看看看看M是怎样拒绝接收。是怎样拒绝接收。(q1,abbab,R)(q1,bbab,AR)(q1,baa,R)(q1,aa,BR)(q1,a,R)(q1,AR)无下一个动作，无下一个动作，w T(M)第38页5给定给定CFG G=（S,A,B,a,b,c,P,S），），其中其中 P为：为：SaAB|aA AbSa|Ab|Bc|b，求一个求一个PDA M，使得使得T(M)=

31、L(G)。解解:(1)先简化先简化G，因为因为G中无中无产生式和单一产生式，所产生式和单一产生式，所以只去掉无用符号：以只去掉无用符号：对对G应用引理应用引理3-2.1，执行上述算法，执行上述算法，得到结果以下表所表示：得到结果以下表所表示：得得G=(S,A,a,b,c,P,S)P：SaA AbSa|Ab|b，循环次数i 初值 1 2 3OLDNEWA,SA AA,SA,S第39页 P：SaA AbSa|Ab|b，再对再对G应用引理应用引理3-2.2处理，执行算法结果以下表所表示：处理，执行算法结果以下表所表示：得得G=(S,A,a,b,P,S)P:SaA AbSa|Ab|b，(2)将将G变成

32、变成GNF形式形式 先变成：先变成：SaA,AbSD|Ab|b,D a，处理左递归处理左递归AAb|bSD|b,变成：变成：AbSD|b|bSDZ|bZ,Zb|bZ最终得：最终得：SaA，AbSD|b|bSDZ|bZ,Zb|bZ，D a循环次数i 初值 1 2 3 S S,A S,A T a a,b 第40页 SaA，AbSD|b|bSDZ|bZ,Zb|bz，D a，(3)依据上述文法，结构依据上述文法，结构PDAM使得使得N(M)=L(G)M=(q,a,b,S,A,D,Z,q,S,):由由SaA得：得：(q,a,S)=(q,A)由由AbSD|b|bSDZ|bZ得：得：(q,b,A)=(q,S

33、D),(q,),(q,SDZ),(q,Z)由由Zb|bz得：得：(q,b,Z)=(q,),(q,Z)由由D a 得：得：(q,a,D)=(q,)(4)依据依据M变成变成M,使得使得T(M)=N(M).M=(q0,q,q1,a,b,S,A,D,Z,E,q0,E,q1):(q0,E)=(q,SE)(q,a,S)=(q,A)(q,b,A)=(q,SD),(q,),(q,SDZ),(q,Z)(q,b,Z)=(q,),(q,Z)(q,a,D)=(q,)(q,E)=(q1,)第41页6给定给定PDA M=(q0,q1,0,1,Z0,X,q0,)，其中其中以下：以下：(q0,1,Z0)=(q0,XZ0)(q

34、0,1,X)=(q0,XX)(q0,0,X)=(q1,X)(q0,Z0)=(q0,)(q1,1,X)=(q1,)(q1,0,Z0)=(q0,Z0)求一个求一个CFG G 使得使得L(G)=N(M).解解：令令M=(K,q0,Z0,)，N(M)=L。结构一个结构一个CFG G=(,S)，其中其中 q,A,p|q,pK,AS =0,1 S,q0,Z0,q0,q0,Z0,q1,q1,Z0,q0,q1,Z0,q1,q0,X,q0,q0,X,q1,q1,X,q0,q1,X,q1 P中产生式有三种类型：中产生式有三种类型：第42页1对任何对任何qK,有有 Sq0,Z0,q。1）Sq0,Z0,q0 2）Sq

35、0,Z0,q12 2对对K K中任何中任何q,q1,q2,qm,qm+1=p，任何任何a，任何任何A,B1,B2,Bm，只要只要(q,a,A)中含有中含有(q1,B1B2Bm)，则有产生式则有产生式 q,A,paq1,B1,q2q2,B2,q3qm,Bm,p。由由(q0,1,Z0)=(q0,XZ0)3）q0,Z0,q01q0,X,q0q0,Z0,q04）q0,Z0,q01q0,X,q1q1,Z0,q05）q0,Z0,q11q0,X,q0q0,Z0,q16）q0,Z0,q11q0,X,q1q1,Z0,q1第43页由由(q0,1,X)=(q0,XX)得得 7）q0,X,q01q0,X,q0q0,X

36、,q0 8）q0,X,q01q0,X,q1q1,X,q0 9）q0,X,q11q0,X,q0q0,X,q1 10）q0,X,q11q0,X,q1q1,X,q1由由(q0,0,X)=(q1,X)得得 11）q0,X,q00q1,X,q0 12）q0,X,q10 q1,X,q1由由(q1,0,Z0)=(q0,Z0)得得 13）q1,Z0,q00q0,Z0,q0 14）q1,Z0,q10 q0,Z0,q1第44页3 3对对任何任何q,pK，任何任何a,任何任何A，假如有假如有(q,a,A)中含有中含有(p,)，则则有有产产生式生式 q,A,pa。由由(q0,Z0)=(q0,)得得 15）q0,Z0,

37、q0 由由(q1,1,X)=(q1,)得得 16）q1,X,q11 下面对这些产生式进行整理。下面对这些产生式进行整理。第45页 1）Sq0,Z0,q0 2）Sq0,Z0,q1 3）q0,Z0,q01q0,X,q0q0,Z0,q0 4）q0,Z0,q01q0,X,q1q1,Z0,q0 5）q0,Z0,q11q0,X,q0q0,Z0,q1 6）q0,Z0,q11q0,X,q1q1,Z0,q1 7）q0,X,q01q0,X,q0q0,X,q0 8）q0,X,q01q0,X,q1q1,X,q0 9）q0,X,q11q0,X,q0q0,X,q1 10）q0,X,q11q0,X,q1q1,X,q1 11

38、）q0,X,q00q1,X,q0 12）q0,X,q10 q1,X,q1 13）q1,Z0,q00q0,Z0,q0 14）q1,Z0,q10 q0,Z0,q1 15）q0,Z0,q0 16）q1,X,q11 无产生式无产生式无产生式无产生式死循环死循环无产生式无产生式无产生式无产生式无产生式无产生式将将14)代入后，死循环代入后，死循环去掉去掉6)后后,无产生式无产生式去掉去掉5)6)后后,无产生式无产生式第46页最终得：最终得：1）Sq0,Z0,q0 4）q0,Z0,q01q0,X,q1q1,Z0,q010）q0,X,q11q0,X,q1q1,X,q112）q0,X,q10 q1,X,q11

39、3）q1,Z0,q00q0,Z0,q015）q0,Z0,q016）q1,X,q11 第47页7求证下面语言求证下面语言L不是不是CFL，L=a k|k是个素数是个素数。证实：证实：(1)假设假设L是是CFL。(2)令令n是是L满足满足CFL泵作用引理常数。泵作用引理常数。(3)取取zam，mn 且且m是个素数。是个素数。|z|=mn,依据依据CFL泵作用引理，可将泵作用引理，可将z写成写成 z=uvwxy 形式，其中形式，其中|vwx|n,|vx|1,且对任何且对任何i0 有有 uviwxiyL。(4)令令u=an1,v=an2,w=an3,x=an4,y=an5,于是于是|vx|=n2+n41,n1+n2+n3+n4+n5=m,z=uvwxy=an1+n2+n3+n4+n5=a m,uviwxiy=an1+in2+n3+in4+n5=am+(i-1)n2+(i-1)n4=am+(i-1)(n2+n4)取取i=m+1,则则 uvm+1wxm+1y=am+(m+1-1)(n2+n4)=am+m(n2+n4)=am(1+n2+n4)因为因为n2+n4 1，故故1+n2+n4 2,而而m2,所以所以m(1+n2+n4)不是素不是素数，故数，故 uvm+1wxm+1y L，产生矛盾。所以产生矛盾。所以L不是不是CFL。第48页