计算理论课后习题答案ppt课件

第一章习题,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的派生过程。解：SABC0ADC0AB0C01AE0C01A0EC01A0B1C01AB01C011AE01C011A0E1C011A01EC011A01B1C011A0B11C011AB011C0110AD011C0110A0D11C0110A01D1C0110A011DC0110A011B0C0110A01B10C0110A0B110C0110AB0110C01100110C01100110,1,2设计下列各文法G，使得它们分别是：（1）G是个上下文无关文法，且L(G)=aibjcki,j,k1。（2）G是个正规文法，且L(G)=aibjcki,j,k1。（3）G是个上下文无关文法，且L(G)=wwRw0,1+。其中wR是w的逆转，例如w=001,则wR=100.解：设计一个文法G要验证：凡是符合要求的句子G都能产生出来；G产生出来的所有句子都是符合要求的。(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结尾。解：,4,2设计二个FAM1和M2，分别满足T(M1)=02ii是自然数T(M2)=02i+1i=0,1,2,3,4,解：M1：,5,3.给定NFAM1=(p,q,r,s,0,1,p,s)，如下表所示。构造一个DFAM2，使得T(M1)=T(M2)。解：令M2=(K,q0,F),其中K2K，K中的元素是由K的子集q1,q2,qi构成，但是要把子集q1,q2,qi作为的一个状态看待，因此把此子集写成q1,q2,qi。q0=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,6,q0=p,K和F以后确定。：,p,0,1,p,q,p,p,q,p,q,r,p,r,p,r,p,q,s,p,p,q,r,p,q,r,s,p,r,p,q,s,p,q,r,s,p,r,s,p,r,s,p,q,s,p,s,p,s,p,q,s,p,s,p,q,r,s,p,q,r,s,p,r,s,K=p,p,q,p,r,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,s,0,1,0,0,0,0,0,0,1,0,1,1,1,1,1,1,7,4.将下面的-NFAM等价变换成NFAM。,：对任何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,因为fCLOSURE(a)=a,b,所以F=F=f：qK,任何a,(q,a)=(q,a)。,在计算(q,a)时，要将a理解成a路径！,例如(a,0)=(a,0)=c,e,d,b。,:,0,1,abcdef,c,e,d,b,d,b,d,b,f,f,d,b,f,d,b,f,f,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,aaaaaa,=a*于是上式aa*b+b=a+b+b=(a+)b=a*b,10,6构造一个FAM，使得T(M)的正规表达式为01+(0+1)*1)*。解：1.分解表达式，找出基本单元：0,1,01,1。设计接收这些基本单元的自动机如下：,11,2.组装：（按照优先权从高到低）01+(0+1)*1)*,1,0,1,0,1,12,7给定FAM如下图所示，求它所接收的语言T(M)的正规表达式。解：,13,14,8.将下面有限自动机简化(要求有简化过程)。解：一.定义K上等价关系给定DFAM=(K,q0,F)，p,qK,pq对x*,有(p,x)F(q,x)F如果pq也称p与q是不可区分的。二.商集K/三的逆关系pqx(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)恰有一个在F中)如果pq,称p与q是可区分的。判断pq是比较容易的。,15,4判断可区分状态对的算法引理2-1设M=(K,q0,F)是DFA，则状态对(p,q)是可区分的(即pq)，当且仅当在下面算法中(p,q)格写上。begin1forpF,qK-F,do给(p,q)格写；2forFF或(K-F)(K-F)中每个状态对(p,q)(pq)，do3ifa，使得格(p,a),(q,a)内已经写上，thenbegin4给(p,q)格写；5如果刚刚写上的格内有先前写入的状态对，此状态对的格同时也写入。反复执行5,直到写入的格内没有先前写入的状态对为止；endelse/*格(p,a),(q,a)内无*/6for每个a,do7把(p,q)写入格(p,a),(q,a)内，除非(p,a)=(q,a)。end,16,执行此算法的结果用一个表表示，实际上，执行此算法的过程就是向这个表内写入“”的过程。,(b,d),(a,b):,be,?,(a,c):,ba,(a,d):,bf,(b,c):,(b,d):,(c,d):,(e,f):,ea,ef,fe,af,dd,fe,得：bd,ef,aa,cc,17,于是K/a,b,d,c,e,f，五构造简化的有限自动机定理2-5.1给定DFAM(K,q0,F)，可根据引理2-1中的算法构造出除去不可达状态的具有更少状态的DFAM，使得T(M)=T(M)。证明：先对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,eF=eM=(K,a,F)=(a,b,c,e,0,1,a,e)(q,a)=(q,a),:,01,abce,b,c,b,e,a,a,e,e,19,9给定DFAM如图所示。求一个左线性文法G，使得L(G)=T(M)。解：有两种方法。方法11.先将M逆转成M：,2.根据M构造右线性文法G：,SA|C|A0BB0A|0C|1C|0C1A|1B|1,3.将G逆转成左线性文法G:,SA|C|AB0BA0|C0|C1|0CA1|B1|1,P=qap|(q,a)=pqa|(q,a)F。,20,方法21.先根据M构造右线性文法G：A0B|1C|1(其中A是开始变元)B0A|1C|0|1C0B|1B2.再将G直接变成左线性文法G:根据定理：(1)S,当且仅当SP；(2)Ai,当且仅当SAiP；(3)AiAj,当且仅当AjAiP；(4)SAj,当且仅当AjP。(1)由A1得:A1(2)由A0B得:B0由A1C得:C1(3)由B0A得:AB0由B1C得:CB1由C0B得:BC0由C1B得:BC1(4)由B0得:AB0由B1得:AB1,21,方法21.先根据M构造右线性文法G：A0B|1C|1|(其中A是开始变元)B0A|1C|0|1C0B|1B因开始变元A出现在产生式右侧，故引入新的开始变元S，SA(其中S是开始变元)A0B|1C|1|B0A|1C|0|1C0B|1B,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得:AB0由B1C得:CB1由C0B得:BC0由C1B得:BC1(4)由A1得:SA1由A得:SA由B0得:SB0由B1得:SB1,23,整理得左线性文法G:SA1|B0|B1|AAB0|BA0|C0|C1CA1|B1表面上看与方法1得结果略有些不同SA|C|AB0BA0|C0|C1|0CA1|B1|1,24,10首先构造一个右线性文法G，使得L(G)=aibj|i,j0ck|k0再构造一个有限自动机M，使得T(M)=L(G)。解：令G=(S,A,B,C,a,b,c,P,S)P:SA|C|AaA|B|BbB|b|CcC|c|令M(S,A,B,C,a,b,c,S,E),c,A,a,b,25,11给定右线性文法G=(S,B,C,D,0,1,P,S)，其中P：SBC，B0B1B011,试求一个FAM，使得T(M)=L(G)。C0D1C,D0C1D解：此题与第10题类似。要将G变成简单右线性文法，唯一要处理的产生式是B011，将它变成：B0F,F1G,G1,26,12.证明Lai|i是个素数不是正规集。证明:(1)假设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=am,uviw=an1+in2+n3=a(n1+n2+n3)+(i-1)n2=am+(i-1)n2取i=m+1,则uvm+1w=am+(m+1-1)n2=am+mn2=am(1+n2)由于n21，所以1+n22,而m2,所以m(1+n2)不是素数，故uvm+1wL，产生矛盾。所以L不是正规集。,27,第三章习题,1给定CFGG=(S,A,B,C,a,b,c,P,S)，其中，P：SA|B,AAb|bS|C|b,BAB|Ba,CASb,去掉G中的无用符号和单一生成式。解：定义：给定CFGG=(,S)，如果在G中存在派生S*X*w，其中w*，X，则称符号X是有用的，否则X是无用的。利用两个引理，去掉无用符号。注意：一定是先应用引理3-2.1,后应用引理3-3.2!,28,引理3-2.1给定CFGG=(,S)，且L(G)，可以找到一个与G等价的CFGG=(,S)，使得每个A，都有w*，且在G中有A*w。证明：1）求的算法：beginOLD:=NEW:=A|AwP且w*WhileOLDNEWdobeginOLD:=NEWNEW:=OLDA|AP,且(OLD)*end:=NEW,end,29,引理3-2.2给定CFGG=(,S)，可以找到一个与G等价的CFGG，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,CASb,对G应用引理3-2.1，执行上述算法，得到的结果如下表所示。,循环次数i初值123,OLD,NEW,A,C,S,A,C,A,C,A,C,S,A,C,S,最后得GCFGG=(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处理，执行算法的结果如下表所示：,最后得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|AS|b,CAS|b但是，可以看出C是无用符号，所以CAS|b也被去掉。最后得：G=(S,A,b,P,S)P:SAb|bS|AS|b,AAb|bS|AS|b,33,2给定CFGG=(S,A,B,C,a,b,P,S)，其中，P：SABC,ABB|,BCC|a,CAA|b,去掉G中的生成式。解：首先求出可为零的变元，即可以推出的变元。显然有A、C、B和S。如果AX1X2XnP，则将所有形如A12n的产生式都加到P中，其中如果Xi不是可为零的，则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给定CFGG=(S,A,0,1,P,S)，其中，P：SAA0,ASS1,将G写成GNF形式。解：此时G已经具备CNF形式。(ABC,Da)(1)变元重新命名：令A1=S,A2=A,P:A1A2A2|0,A2A1A1|1,(2)处理A2A1A1|1,变成：A2A2A2A1|0A1|1,(3)处理左递归A2A2A2A1|0A1|1,变成：A20A1|1|0A1Z2|1Z2,Z2A2A1|A2A1Z2,(4)处理A1A2A2|0，得A10A1A2|1A2|0A1Z2A2|1Z2A2|0(5)处理Z2A2A1|A2A1Z2,分别得：Z20A1A1|1A1|0A1Z2A1|1Z2A1Z20A1A1Z2|1A1Z2|0A1Z2A1Z2|1Z2A1Z2,35,最后得G=(A1,A2,Z2,0,1,P,A1)P:A10A1A2|1A2|0A1Z2A2|1Z2A2|0A20A1|1|0A1Z2|1Z2,Z20A1A1|1A1|0A1Z2A1|1Z2A1Z20A1A1Z2|1A1Z2|0A1Z2A1Z2|1Z2A1Z2,36,4构造一个PDAM，使得T(M)=w|wa,b*w中a,b的个数相等。解：设计思想：有两个状态q1和q2：q1是开始状态，q2是终止状态。栈内符号：A，B，R(R是开始时栈内符号)。开始时：读a，向栈压入A；读b，向栈压入B。之后：当读a时：如果栈顶是A，再向栈压入一个A；如果栈顶是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识别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)无下一个动作，wT(M),38,5给定CFGG=（S,A,B,a,b,c,P,S），其中P为：SaAB|aAAbSa|Ab|Bc|b，求一个PDAM，使得T(M)=L(G)。解:(1)先简化G，因为G中无产生式和单一产生式，所以只去掉无用符号：对G应用引理3-2.1，执行上述算法，得到的结果如下表所示：得G=(S,A,a,b,c,P,S)P：SaAAbSa|Ab|b，,循环次数i初值123,OLD,NEW,A,S,A,A,A,S,A,S,39,P：SaAAbSa|Ab|b，再对G应用引理3-2.2处理，执行算法的结果如下表所示：得G=(S,A,a,b,P,S)P:SaAAbSa|Ab|b，(2)将G变成GNF形式先变成：SaA,AbSD|Ab|b,Da，处理左递归AAb|bSD|b,变成：AbSD|b|bSDZ|bZ,Zb|bZ最后得：SaA，AbSD|b|bSDZ|bZ,Zb|bZ，Da,40,SaA，AbSD|b|bSDZ|bZ,Zb|bz，Da，(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,SD),(q,),(q,SDZ),(q,Z)由Zb|bz得：(q,b,Z)=(q,),(q,Z)由Da得：(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给定PDAM=(q0,q1,0,1,Z0,X,q0,)，其中如下：(q0,1,Z0)=(q0,XZ0)(q0,1,X)=(q0,XX)(q0,0,X)=(q1,X)(q0,Z0)=(q0,)(q1,1,X)=(q1,)(q1,0,Z0)=(q0,Z0)求一个CFGG使得L(G)=N(M).解：令M=(K,q0,Z0,)，N(M)=L。构造一个CFGG=(,S)，其中q,A,p|q,pK,AS=0,1S,q0,Z0,q0,q0,Z0,q1,q1,Z0,q0,q1,Z0,q1,q0,X,q0,q0,X,q1,q1,X,q0,q1,X,q1P中产生式有三种类型：,42,1对任何qK,有Sq0,Z0,q。1）Sq0,Z0,q02）Sq0,Z0,q12对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,q08）q0,X,q01q0,X,q1q1,X,q09）q0,X,q11q0,X,q0q0,X,q110）q0,X,q11q0,X,q1q1,X,q1由(q0,0,X)=(q1,X)得11）q0,X,q00q1,X,q012）q0,X,q10q1,X,q1由(q1,0,Z0)=(q0,Z0)得13）q1,Z0,q00q0,Z0,q014）q1,Z0,q10q0,Z0,q1,44,3对任何q,pK，任何a,任何A，如果有(q,a,A)中含有(p,)，则有产生式q,A,pa。由(q0,Z0)=(q0,)得15）q0,Z0,q0由(q1,1,X)=(q1,)得16）q1,X,q11下面对这些产生式进行整理。,45,1）Sq0,Z0,q02）Sq0,Z0,q13）q0