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

《计算理论课后习题答案.ppt》由会员分享，可在线阅读，更多相关《计算理论课后习题答案.ppt（49页珍藏版）》请在三一办公上搜索。

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的派生过程。解：SABC0ADC0AB0C01AE0C01A0EC01A0B1C01AB01C011AE01C011A0E1C011A01EC011A01B1C011A0B11C011AB011C0110AD011C0110A0D11C0110A01D1C0110A011DC0110A011B0C0110A01B10C0110A0B110C0110AB0110C0110

2、0110C01100110,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产生出来的所有句子都是符合要求的。(1)G=(S,A,B,C,a,b,c,P,S)P:SABC,AaA|a,BbB|b,CcC|c,(2)G=(S,A,B,C,a,b,c,P,S)P:SaA,AaA|bB,BbB|cC,Cc

3、C|(3)G=(S,0,1,P,S)P:S0S0|1S1|00|11,第二章 习题,1设计一个有限自动机(FA)M，使得T(M)中的每个句子w同时满足下面三个条件：1)wa,b,*；2)|w|是3的整数倍；3)w以a开头，以b结尾。解：,2设计二个FA M1和M2，分别满足 T(M1)=02ii是自然数 T(M2)=02i+1i=0,1,2,3,4,解：M1：,3.给定NFA M1=(p,q,r,s,0,1,p,s)，如下表所示。构造一个DFA M2，使得T(M1)=T(M2)。解：令 M2=(K,q0,F),其中 K2K，K中的元素是由K的子集q1,q2,qi构成，但是要把子集q1,q2,q

4、i作为的一个状态看待，因此把此子集写成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,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,

5、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,4.将下面的-NFA M等价变换成NFA M。,：对任何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),因为fCLOSURE(a)=a,b,所以F=F=f：qK,任何a,(q,a)=(q,a)。,在计算(q,a)时，要将a理解成a路径！,例如(a,0)=(a,0)=c,e,d,

6、b。,:,0,1,abcdef,c,e,d,b,d,b,d,b,f,f,d,b,f,d,b,f,f,d,b,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,6构造一个FA M，使得T(M)的正规表达式为01+(0+1)*1)*。解：1.分解表达式，找出基本单元：0,1,01,1。设计接收这些基本单元的自动

7、机如下：,2.组装：（按照优先权从高到低）01+(0+1)*1)*,1,0,1,0,1,7给定FA M如下图所示，求它所接收的语言T(M)的正规表达式。解：,8.将下面有限自动机简化(要求有简化过程)。解：一.定义K上等价关系给定DFA M=(K,q0,F)，p,qK,pq 对 x*,有(p,x)F(q,x)F如果pq 也称p与q是不可区分的。二.商集K/三的逆关系 pq 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)恰有一个在F中)如果pq,称p与q是可区分的。判断pq是比较容易的。,4判断可区分状态对的算法

8、引理2-1 设M=(K,q0,F)是DFA，则状态对(p,q)是可区分的(即pq)，当且仅当在下面算法中(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 begin4 给(p,q)格写；5 如果刚刚写上的格内有先前写入的状态对，此状态对 的格同时也写入。反复执行5,直到写入的格内没 有先前写入的状态对为止；end else/*格(p,a),(q,a)内无*/6for 每个a,do 7把(p,q)写入格(p,a),(q,a)内，除非(

9、p,a)=(q,a)。end,执行此算法的结果用一个表表示，实际上，执行此算法的过程就是向这个表内写入“”的过程。,(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,于是 K/a,b,d,c,e,f，五构造简化的有限自动机定理2-5.1 给定DFA M(K,q0,F)，可根据引理2-1中的算法构造出除去不可达状态的具有更少状态的DFA M，使得T(M)=T(M)。证明：先对M用引理2-1中的算法求出K/。再构造M：M=(K,q0,F)，其中 K=q|

10、qK/且在M中q是从q0 可达的状态 F=q|qF：对任何qK，任何a,(q,a)=(q,a),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),:,0 1,abce,b,c,b,e,a,a,e,e,9给定DFA M如图所示。求一个左线性文法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|

11、B1|1,P=qap|(q,a)=pqa|(q,a)F。,方法21.先根据M构造右线性文法G：A0B|1C|1(其中A是开始变元)B0A|1C|0|1 C0B|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 得:A B0 由B1C 得:CB1 由C0B 得:BC0 由C1B 得:BC1(4)由 B0 得:AB0 由B1 得:AB1,方法21.先根据M构造右线性文法G：A0B|1C|1|(其

12、中A是开始变元)B0A|1C|0|1 C0B|1B因开始变元A出现在产生式右侧，故引入新的开始变元S，SA(其中S是开始变元)A0B|1C|1|B0A|1C|0|1 C0B|1B,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 得:BC0 由C1B 得:BC1(4)由A1 得:SA1 由A 得:SA 由 B0 得:SB0 由B1 得:SB1,整理得左线

13、性文法G:SA1|B0|B1|A A B0|BA0|C0|C1 CA1|B1表面上看与方法1得结果略有些不同 SA|C|AB0 BA0|C0|C1|0 CA1|B1|1,10首先构造一个右线性文法G，使得 L(G)=ai bj|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,11给定右线性文法G=(S,B,C,D,0,1,P,S)，其中P：SBC，B0B1B011,试求一个FA M，使得 T(M)=L(G)。C0D1C,

14、D0C1D解：此题与第10题类似。要将G变成简单右线性文法，唯一要处理的产生式是 B011，将它变成：B0F,F1G,G 1,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=a m,uviw=an1+in2+n3=a(n1+n2+n3)+

15、(i-1)n2=am+(i-1)n2取i=m+1,则 uvm+1w=am+(m+1-1)n2=am+mn2=am(1+n2)由于n21，所以1+n2 2,而m2,所以m(1+n2)不是素数，故 uvm+1wL，产生矛盾。所以L不是正规集。,第三章 习题,1给定CFG G=(S,A,B,C,a,b,c,P,S)，其中，P：SA|B,AAb|bS|C|b,BAB|Ba,CASb,去掉G中的无用符号和单一生成式。解：定义：给定CFG G=(,S)，如果在G中存在派生S*X*w，其中w*，X，则称符号X是有用的，否则X是无用的。利用两个引理，去掉无用符号。注意：一定是先应用引理3-2.1,后应用引理3

16、-3.2!,引理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,引理3-2.2 给定CFG G=(,S)，可以找到一个与G等价的CFG G，G=(,S)，使得每个X()，都有,()*，且在G中有派生S*X。证明：1执行下面迭代算法求和。1）置初值：:=S，:=;2）如果A，在P中又有产生式A1|2|m，则可以将1,

17、2,m中的所有变元加到中，将1,2,m中的所有终极符加到中中。重复2)。3）若没有新的符号可加入到、中，算法停止。最后得到、。,P：SA|B,AAb|bS|C|b,BAB|Ba,CASb,对G应用引理3-2.1，执行上述算法，得到的结果如下表所示。,循环次数i 初值 1 2 3,OLD,NEW,A,C,S,A,C,A,C,A,C,S,A,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：,P：SA,AAb|bS|C|b,CAS|b再对G用引理3-2.2处理，执行算法

18、的结果如下表所示：,最后得G=(S,A,C,b,P,S)P:SA,AAb|bS|C|b,CAS|b实际上只去掉了无用符号a和c。,下面对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

19、|b,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不是可为零的，则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,3给定CFG G=(S,A,0,1,P,S)，其中，P：SAA0,ASS1,将G写成GNF形式。解：此时G

20、已经具备CNF形式。(ABC,Da)(1)变元重新命名：令A1=S,A2=A,P:A1A2A2|0,A2A1A1|1,(2)处理A2 A1A1|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,最后得G=(A1,A2,Z2,0,

21、1,P,A1)P:A1 0A1A2|1A2|0A1Z2A2|1Z2A2|0 A20A1|1|0A1Z2|1Z2,Z2 0A1A1|1A1|0A1Z2A1|1Z2A1 Z2 0A1A1Z2|1A1Z2|0A1Z2A1Z2|1Z2A1Z2,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；如果栈顶是B，则B退栈。当读b时：如果栈顶是B，再向栈压入一个B；如果栈顶是A，则A

22、退栈。如果w中a,b的个数相等，则M读完w后，栈顶应该是R，此时M进入终止状态q2。,令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是如何

23、拒绝接收的。(q1,abbab,R)(q1,bbab,AR)(q1,baa,R)(q1,aa,BR)(q1,a,R)(q1,AR)无下一个动作，wT(M),5给定CFG G=（S,A,B,a,b,c,P,S），其中 P为：SaAB|aA AbSa|Ab|Bc|b，求一个PDA M，使得T(M)=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 3,OLD,NEW,A,S,A,A,A,S,A,S,P：SaA Ab

24、Sa|Ab|b，再对G应用引理3-2.2处理，执行算法的结果如下表所示：得G=(S,A,a,b,P,S)P:SaA AbSa|Ab|b，(2)将G变成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,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,

25、SD),(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,),6给定PDA M=(q0,q1,0,1,Z0,X,q0,)，其中如下：(q0,1,Z0)=(q0,XZ0)(q0,1,X)=(q0,XX)(q0,0,X

26、)=(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中产生式有三种类型：,1对任何qK,有 Sq0,Z0,q。1）Sq0,Z0,q0 2）Sq0,Z0,q12对K中任何q,q1,q2,qm,qm+1=p，任何a，任何A,B1,B2,Bm，只要(q

27、,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,由(q0,1,X)=(q0,XX)得 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

28、由(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,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 下面对这些产生式进行整理。,1）Sq0,Z0,q0 2）Sq0,Z0,q1 3）q0,Z0,q01q0,X,q0q0,Z0,q0 4）q0,Z0,q01

29、q0,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）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,无产生式,无产生式,死循环,无产生式,无产生式

30、,无产生式,将14)代入后，死循环,去掉6)后,无产生式,去掉5)6)后,无产生式,最后得：1）Sq0,Z0,q0 4）q0,Z0,q01q0,X,q1q1,Z0,q010）q0,X,q11q0,X,q1q1,X,q112）q0,X,q10 q1,X,q113）q1,Z0,q00q0,Z0,q015）q0,Z0,q016）q1,X,q11,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,

31、且对任何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。,谢 谢！,放映结束 感谢各位观看！,让我们共同进步,