計(jì)算理論課后習(xí)題答案PPT課件

.,1,第一章習(xí)題,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,.,2,2設(shè)計(jì)下列各文法G，使得它們分別是：（1）G是個(gè)上下文無關(guān)文法，且L(G)=aibjcki,j,k1。（2）G是個(gè)正規(guī)文法，且L(G)=aibjcki,j,k1。（3）G是個(gè)上下文無關(guān)文法，且L(G)=wwRw0,1+。其中wR是w的逆轉(zhuǎn)，例如w=001,則wR=100.解：設(shè)計(jì)一個(gè)文法G要驗(yàn)證：凡是符合要求的句子G都能產(chǎn)生出來；G產(chǎn)生出來的所有句子都是符合要求的。(1)G=(S,A,B,C,a,b,c,P,S)P:SABC,AaA|a,BbB|b,CcC|c,.,3,(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,.,4,第二章習(xí)題,1設(shè)計(jì)一個(gè)有限自動(dòng)機(jī)(FA)M，使得T(M)中的每個(gè)句子w同時(shí)滿足下面三個(gè)條件：1)wa,b,*；2)|w|是3的整數(shù)倍；3)w以a開頭，以b結(jié)尾。解：,.,5,2設(shè)計(jì)二個(gè)FAM1和M2，分別滿足T(M1)=02ii是自然數(shù)T(M2)=02i+1i=0,1,2,3,4,解：M1：,.,6,3.給定NFAM1=(p,q,r,s,0,1,p,s)，如下表所示。構(gòu)造一個(gè)DFAM2，使得T(M1)=T(M2)。解：令M2=(K,q0,F),其中K2K，K中的元素是由K的子集q1,q2,qi構(gòu)成，但是要把子集q1,q2,qi作為的一個(gè)狀態(tà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當(dāng)且僅當(dāng)(q1,q2,qi,a)=p1,p2,pj,.,7,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,.,8,4.將下面的-NFAM等價(jià)變換成NFAM。,：對任何qK,任何a,(q,a)=(q,a)。,解：M=(K,q0,F)，q0是M的開始狀態(tài)，其中,公式(1)：對于qK,(q,)=-CLOSURE(q),公式(2)：對于qK,w*,a,(q,wa)=-CLOSURE(q,w),a),.,9,因?yàn)閒CLOSURE(a)=a,b,所以F=F=f：qK,任何a,(q,a)=(q,a)。,在計(jì)算(q,a)時(shí)，要將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,.,10,5化簡正規(guī)表達(dá)式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,.,11,6構(gòu)造一個(gè)FAM，使得T(M)的正規(guī)表達(dá)式為01+(0+1)*1)*。解：1.分解表達(dá)式，找出基本單元：0,1,01,1。設(shè)計(jì)接收這些基本單元的自動(dòng)機(jī)如下：,.,12,2.組裝：（按照優(yōu)先權(quán)從高到低）01+(0+1)*1)*,1,0,1,0,1,.,13,7給定FAM如下圖所示，求它所接收的語言T(M)的正規(guī)表達(dá)式。解：,.,14,.,15,8.將下面有限自動(dòng)機(jī)簡化(要求有簡化過程)。解：一.定義K上等價(jià)關(guān)系給定DFAM=(K,q0,F)，p,qK,pq對x*,有(p,x)F(q,x)F如果pq也稱p與q是不可區(qū)分的。二.商集K/三的逆關(guān)系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)恰有一個(gè)在F中)如果pq,稱p與q是可區(qū)分的。判斷pq是比較容易的。,.,16,4判斷可區(qū)分狀態(tài)對的算法引理2-1設(shè)M=(K,q0,F)是DFA，則狀態(tài)對(p,q)是可區(qū)分的(即pq)，當(dāng)且僅當(dāng)在下面算法中(p,q)格寫上。begin1forpF,qK-F,do給(p,q)格寫；2forFF或(K-F)(K-F)中每個(gè)狀態(tài)對(p,q)(pq)，do3ifa，使得格(p,a),(q,a)內(nèi)已經(jīng)寫上，thenbegin4給(p,q)格寫；5如果剛剛寫上的格內(nèi)有先前寫入的狀態(tài)對，此狀態(tài)對的格同時(shí)也寫入。反復(fù)執(zhí)行5,直到寫入的格內(nèi)沒有先前寫入的狀態(tài)對為止；endelse/*格(p,a),(q,a)內(nèi)無*/6for每個(gè)a,do7把(p,q)寫入格(p,a),(q,a)內(nèi)，除非(p,a)=(q,a)。end,.,17,執(zhí)行此算法的結(jié)果用一個(gè)表表示，實(shí)際上，執(zhí)行此算法的過程就是向這個(gè)表內(nèi)寫入“”的過程。,(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,.,18,于是K/a,b,d,c,e,f，五構(gòu)造簡化的有限自動(dòng)機(jī)定理2-5.1給定DFAM(K,q0,F)，可根據(jù)引理2-1中的算法構(gòu)造出除去不可達(dá)狀態(tài)的具有更少狀態(tài)的DFAM，使得T(M)=T(M)。證明：先對M用引理2-1中的算法求出K/。再構(gòu)造M：M=(K,q0,F)，其中K=q|qK/且在M中q是從q0可達(dá)的狀態(tài)F=q|qF：對任何qK，任何a,(q,a)=(q,a),.,19,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,.,20,9給定DFAM如圖所示。求一個(gè)左線性文法G，使得L(G)=T(M)。解：有兩種方法。方法11.先將M逆轉(zhuǎn)成M：,2.根據(jù)M構(gòu)造右線性文法G：,SA|C|A0BB0A|0C|1C|0C1A|1B|1,3.將G逆轉(zhuǎn)成左線性文法G:,SA|C|AB0BA0|C0|C1|0CA1|B1|1,P=qap|(q,a)=pqa|(q,a)F。,.,21,方法21.先根據(jù)M構(gòu)造右線性文法G：A0B|1C|1(其中A是開始變元)B0A|1C|0|1C0B|1B2.再將G直接變成左線性文法G:根據(jù)定理：(1)S,當(dāng)且僅當(dāng)SP；(2)Ai,當(dāng)且僅當(dāng)SAiP；(3)AiAj,當(dāng)且僅當(dāng)AjAiP；(4)SAj,當(dāng)且僅當(dāng)AjP。(1)由A1得:A1(2)由A0B得:B0由A1C得:C1(3)由B0A得:AB0由B1C得:CB1由C0B得:BC0由C1B得:BC1(4)由B0得:AB0由B1得:AB1,.,22,方法21.先根據(jù)M構(gòu)造右線性文法G：A0B|1C|1|(其中A是開始變元)B0A|1C|0|1C0B|1B因開始變元A出現(xiàn)在產(chǎn)生式右側(cè)，故引入新的開始變元S，SA(其中S是開始變元)A0B|1C|1|B0A|1C|0|1C0B|1B,.,23,2.再將G直接變成左線性文法G:根據(jù)定理：(1)S,當(dāng)且僅當(dāng)SP；(2)Ai,當(dāng)且僅當(dāng)SAiP；(3)AiAj,當(dāng)且僅當(dāng)AjAiP；(4)SAj,當(dāng)且僅當(dāng)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,.,24,整理得左線性文法G:SA1|B0|B1|AAB0|BA0|C0|C1CA1|B1表面上看與方法1得結(jié)果略有些不同SA|C|AB0BA0|C0|C1|0CA1|B1|1,.,25,10首先構(gòu)造一個(gè)右線性文法G，使得L(G)=aibj|i,j0ck|k0再構(gòu)造一個(gè)有限自動(dòng)機(jī)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,.,26,11給定右線性文法G=(S,B,C,D,0,1,P,S)，其中P：SBC，B0B1B011,試求一個(gè)FAM，使得T(M)=L(G)。C0D1C,D0C1D解：此題與第10題類似。要將G變成簡單右線性文法，唯一要處理的產(chǎn)生式是B011，將它變成：B0F,F1G,G1,.,27,12.證明Lai|i是個(gè)素?cái)?shù)不是正規(guī)集。證明:(1)假設(shè)L是正規(guī)集。(2)令n是L滿足正規(guī)集泵作用引理常數(shù)。(3)取zam，mn且m是個(gè)素?cái)?shù)。|z|=mn,根據(jù)正規(guī)集的泵作用引理，可將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)不是素?cái)?shù)，故uvm+1wL，產(chǎn)生矛盾。所以L不是正規(guī)集。,.,28,第三章習(xí)題,1給定CFGG=(S,A,B,C,a,b,c,P,S)，其中，P：SA|B,AAb|bS|C|b,BAB|Ba,CASb,去掉G中的無用符號(hào)和單一生成式。解：定義：給定CFGG=(,S)，如果在G中存在派生S*X*w，其中w*，X，則稱符號(hào)X是有用的，否則X是無用的。利用兩個(gè)引理，去掉無用符號(hào)。注意：一定是先應(yīng)用引理3-2.1,后應(yīng)用引理3-3.2!,.,29,引理3-2.1給定CFGG=(,S)，且L(G)，可以找到一個(gè)與G等價(jià)的CFGG=(,S)，使得每個(gè)A，都有w*，且在G中有A*w。證明：1）求的算法：beginOLD:=NEW:=A|AwP且w*WhileOLDNEWdobeginOLD:=NEWNEW:=OLDA|AP,且(OLD)*end:=NEW,end,.,30,引理3-2.2給定CFGG=(,S)，可以找到一個(gè)與G等價(jià)的CFGG，G=(,S)，使得每個(gè)X()，都有,()*，且在G中有派生S*X。證明：1執(zhí)行下面迭代算法求和。1）置初值：:=S，:=;2）如果A，在P中又有產(chǎn)生式A1|2|m，則可以將1,2,m中的所有變元加到中，將1,2,m中的所有終極符加到中中。重復(fù)2)。3）若沒有新的符號(hào)可加入到、中，算法停止。最后得到、。,.,31,P：SA|B,AAb|bS|C|b,BAB|Ba,CASb,對G應(yīng)用引理3-2.1，執(zhí)行上述算法，得到的結(jié)果如下表所示。,循環(huán)次數(shù)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實(shí)際上，只去掉了不能推出終極符串的變元B。再對G應(yīng)用引理3-2.2：,.,32,P：SA,AAb|bS|C|b,CAS|b再對G用引理3-2.2處理，執(zhí)行算法的結(jié)果如下表所示：,最后得G=(S,A,C,b,P,S)P:SA,AAb|bS|C|b,CAS|b實(shí)際上只去掉了無用符號(hào)a和c。,.,33,下面對G去掉單一產(chǎn)生式:對任何A,B，如果有A*B，且B1|2|n是P中B的所有非單一產(chǎn)生式，則把所有A1|2|n加到P中。P:SA,AAb|bS|C|b,CAS|b下面去掉單一產(chǎn)生式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是無用符號(hào)，所以CAS|b也被去掉。最后得：G=(S,A,b,P,S)P:SAb|bS|AS|b,AAb|bS|AS|b,.,34,2給定CFGG=(S,A,B,C,a,b,P,S)，其中，P：SABC,ABB|,BCC|a,CAA|b,去掉G中的生成式。解：首先求出可為零的變元，即可以推出的變元。顯然有A、C、B和S。如果AX1X2XnP，則將所有形如A12n的產(chǎn)生式都加到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,.,35,3給定CFGG=(S,A,0,1,P,S)，其中，P：SAA0,ASS1,將G寫成GNF形式。解：此時(shí)G已經(jīng)具備CNF形式。(ABC,Da)(1)變元重新命名：令A(yù)1=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,.,36,最后得G=(A1,A2,Z2,0,1,P,A1)P:A10A1A2|1A2|0A1Z2A2|1Z2A2|0A20A1|1|0A1Z2|1Z2,Z20A1A1|1A1|0A1Z2A1|1Z2A1Z20A1A1Z2|1A1Z2|0A1Z2A1Z2|1Z2A1Z2,.,37,4構(gòu)造一個(gè)PDAM，使得T(M)=w|wa,b*w中a,b的個(gè)數(shù)相等。解：設(shè)計(jì)思想：有兩個(gè)狀態(tài)q1和q2：q1是開始狀態(tài)，q2是終止?fàn)顟B(tài)。棧內(nèi)符號(hào)：A，B，R(R是開始時(shí)棧內(nèi)符號(hào))。開始時(shí)：讀a，向棧壓入A；讀b，向棧壓入B。之后：當(dāng)讀a時(shí)：如果棧頂是A，再向棧壓入一個(gè)A；如果棧頂是B，則B退棧。當(dāng)讀b時(shí)：如果棧頂是B，再向棧壓入一個(gè)B；如果棧頂是A，則A退棧。如果w中a,b的個(gè)數(shù)相等，則M讀完w后，棧頂應(yīng)該是R，此時(shí)M進(jìn)入終止?fàn)顟B(tài)q2。,.,38,令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時(shí)，M識(shí)別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)無下一個(gè)動(dòng)作，wT(M),.,39,5給定CFGG=（S,A,B,a,b,c,P,S），其中P為：SaAB|aAAbSa|Ab|Bc|b，求一個(gè)PDAM，使得T(M)=L(G)。解:(1)先簡化G，因?yàn)镚中無產(chǎn)生式和單一產(chǎn)生式，所以只去掉無用符號(hào)：對G應(yīng)用引理3-2.1，執(zhí)行上述算法，得到的結(jié)果如下表所示：得G=(S,A,a,b,c,P,S)P：SaAAbSa|Ab|b，,循環(huán)次數(shù)i初值123,OLD,NEW,A,S,A,A,A,S,A,S,.,40,P：SaAAbSa|Ab|b，再對G應(yīng)用引理3-2.2處理，執(zhí)行算法的結(jié)果如下表所示：得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,.,41,SaA，AbSD|b|bSDZ|bZ,Zb|bz，Da，(3)根據(jù)上述文法，構(gòu)造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)根據(jù)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,),.,42,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)求一個(gè)CFGG使得L(G)=N(M).解：令M=(K,q0,Z0,)，N(M)=L。構(gòu)造一個(gè)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中產(chǎn)生式有三種類型：,.,43,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)，則有產(chǎn)生式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,.,44,由(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,.,45,3對任何q,pK，任何a,任何A，如果有(q,a,A)中含有(p,)，則有產(chǎn)生式q,A,pa。由(q0,Z0)=(q0,)得15）q0,Z0,q0由(q1,1,X)=(q1,)得16）q1,X,q11下面對這些產(chǎn)生式進(jìn)行整理。,.,46,1）Sq0,Z0,q02）Sq0,Z0,q13）q0,Z0,q01q0,X,q0q0,Z