形式語言與自動機(jī)理論-蔣宗禮-參考答案

1、第三章作業(yè)答案1已知DFAM1與M2如圖3- 18所示。(1) 請分別給出它們在處理字符串(2) 請給出它們的形式描述。(敖雪峰 02282068)1011001的過程中經(jīng)過的狀態(tài)序列。圖3- 18兩個(gè)不同的DFAqoq3qiq3q2q3qiq3；解答:(1)M1在處理1011001的過程屮經(jīng)過的狀態(tài)序列為M2在處理1011001的過程中經(jīng)過的狀態(tài)序列為qq2q3qiq3q2q3qi；考慮到用形式語言表示，用自然語言似乎不是那么容易, 所以用圖上作業(yè)法把它們用正則 表達(dá)式來描述M1: 01 +(00+1 )(11 +0)11 +(10+0)(11 +0)*M2: (01 + 1+000)(01

2、 )*+(001 + 11)(01 + 1 +000)*(陶文嬪 02282085 )2. 構(gòu)造下列語言的DFA(D 0, 1(3) x|x 0, 1但X中不含00的串(設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有 00的子串，就進(jìn)入陷阱狀態(tài))(4) x|x 0 , 1沮x中不含00的串(可接受空字符串，所以初始狀態(tài)也是接受狀態(tài))x|xA0, 1但x中不含形如10110的子串(設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有 00的子串，就進(jìn)入陷阱狀態(tài))(7)x|x0, 1但當(dāng)把x看成二進(jìn)制時(shí)，x模5和3同余，要求當(dāng)x為0時(shí),|x|=1,_ax=0時(shí),x的首字符為11.以0開頭的串不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)DFA在啟動狀態(tài)讀入

3、的符號為0,則進(jìn)入陷阱狀態(tài)2.設(shè)置7個(gè)狀態(tài)：開始狀態(tài)qs,q。：除以5余0的等價(jià)類，除以5余1的等價(jià)類口 2：除以5 余2的等價(jià)類，q3：除以5余3的等價(jià)類，q4：除以5余4的等價(jià)類，接受狀態(tài)qt3.狀態(tài)轉(zhuǎn)移表為狀態(tài)01qoqiq2qiqaq2Q2qoq4q3qiq2q4q3q4(8) x|x0, 1但x的第十個(gè)字符為10,進(jìn)入陷阱狀態(tài))(設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個(gè)字符為(9) x|x 0, 1且x以0開頭以1結(jié)尾(設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài))(10) x|x 0, 1且x中至少含有兩個(gè)10x以0結(jié)尾，則它的長度(11) x|x0, 1且如果x以1結(jié)尾，則它的長度

4、為偶數(shù)；如果 為奇數(shù)可將0,甘的字符串分為4個(gè)等價(jià)類。qo：的等價(jià)類，對應(yīng)的狀態(tài)為終止?fàn)顟B(tài)qi： x的長度為奇且以q2： x的長度為奇且以0結(jié)尾的等價(jià)類q3： x的長度為偶且 1結(jié)尾的等價(jià)類以0結(jié)尾的等價(jià)類q4： X的長度為偶且以1結(jié)尾的等價(jià)類(12)x|x是十進(jìn)制非負(fù)數(shù)(13) ns OO(14) (張友坤 02282061)3(1)00,1Set(q0)=x lx-50,1Set(q0)=；Set(q1)=x | x- - *(3)-=0,1Set(q0)=；Set(q1)=x并且x中不含形如Set(q2)=x |x-并且x中不含形如00的子串00的子串00的子串00的子串Set(q0)=

5、x | x匚-*并且x中不含形如Set(q1)=x | x 并且x中不含形如*=0,1*Set(q0)= x|，并且0或者x中含形如100的子串Set(q1)=x | x三*,并且x中含形如1的子串Set(q2)=x | x 二，并且x中含形如10的子串Set(q3)=x | xr,并且x中含形如101的子串Set(q4)=x| X-,并且x中含形如1011的子串Set(q5)=x| X-,并且x中含形如10110的子串0,1Set(q0)= ； +Set(q1)=x | x0 Set(q2)=x | x-,并且x中不含形如10110的子串而且x中含有1Set(q3)=x | X-,并且x中不

6、含形如10110的子串而且x屮含有1(7)0=0,1 Set(qs)= Set(qe)= 0Set(q1)=x | x, +,并且把x看成二進(jìn)制數(shù)時(shí)，X% 5=1Set(q2)=x | X；，并且把x看成二進(jìn)制數(shù)時(shí)，X% 5=2Set(q3)=x |Set(q4)=x |x 7 ,并且把x看成二進(jìn)制數(shù)時(shí)，x% 5=3x三7 +,并且把x看成二進(jìn)制數(shù)時(shí)，X% 5=4Set(q0)=x |(8)M=Q, *x三7 +,并且把x看成二進(jìn)制數(shù)時(shí)，X% 5=0并且x不為0Q=q o,qi,q2, qo =0,1當(dāng)0=i0AA 1S | 1S 1BB OS | 0將代入SOA； 06,代入SB得S01S|

7、01S 1 OS | 1 0由此可以看出該文法接受的語言為L=（10|01） *，顯然01或10分別是作為整體出現(xiàn)的,所以L（M）中0和1的個(gè)數(shù)相等。7設(shè) DFAM=（Q,、，、，q。，F(xiàn)）,證明：對于-X,y二 *,q Q,、.（q,xy） =、. C （q,x）, y）注：采用歸納證明的思路證明：（周期律02282067）首先對y歸納，對任意x來說，|y| = 0時(shí)，即y=；根據(jù) DFA 定義、（q,；）二口八（q,xy）=、（q,x） =.（. （q, x）, ；）=、（、（q,x）, y）,故原式 成立。當(dāng)|y| = n時(shí)，假設(shè)原式成立，故當(dāng)|y|=n+1時(shí)，不妨設(shè) y = wa, |

8、w| = n, |a| = 1根據(jù) DFA 定義、（q , xa ）二、.（、.（q , x）, a）, a ,故、(q,xy)二、(q,xwa)二、(q,xw),a)二、(q,x), w),a)二、(、(q, x), wa)二 G (q, x), y)原式成立，同理可證，對任意的y來說，結(jié)論也是成立的。綜上所述，原式得證& 證明:對于任意的 DFAMi=(QQ,S,qFi)存在 DFA M 2=(QQ , S ,q,F2),(馮蕊 02282075)使得 L(M 2)=I 一 L ( MJ o證明：(1)構(gòu)造M2。設(shè) DFAM 1=(Q,I,S ,qo,Fi)取 DFA M 2=(Q,工,S

9、 ,qo,Q Fi)(2)證明 L(M2)=工一L ( Mi)對任意x工*=工并且x -x- L(M 2)=工一L ( Mi) ： = S (q,x) Q FA S (q,x):二 Q 并且 S (q,x) Fi 二 x： L(M i)=x,工 一 L ( Mi)9. 對于任意的DFA Mi=(Qi,刀,S i,qoi,Fi)，請構(gòu)造DFA Mg,刀,S 2牛尸2),使得L(M i)=L(M 2)To 其中 L(M)T=X|XT L(M)(褚穎娜 02282072)構(gòu)造 s -NFA M 使得 L(M)=L(M 1)取NFA M=( Q,刀,S , q。q o)其41) Q= QiU q ,

10、q * Qi2) 對于- q,p Qi,aE,如果 Si(q,a)=p,q S (p,a)3) S (q。, e )= Fi(2) 證明：L(M)=L(M i)T對- x=aia2-am L(M)qo ai a2 am 卜qfaia2am 卜a qia2am卜aia2 q2am 卜ai a2qm-i am卜 aa2 amqoi其中 qt S (qo, J, qi% as), qsg, a2), qOism-i, am)并且 qz貝g S i(qoi, am)= qm-i, S i(qm-i, am-i)= qm-2,*S i(q2, S2)= qiS i(qi, ai)= qf因止匕 Qoi

11、am am-i ai 卜 am qm-i am-i.ai b am 3m-i -q2 S2 Si b am am-i-a2 qiSi卜 am am-i -a2 aiqf因此 am am-i ai L(M i)即 xT L(M i)同理可證對于 x=aia2-am L(M i) xT=am am-i ai L(M i)L(M)=L(M i)T 得證(3) 將e-NFA M確定化首先構(gòu)造與 e-NFA M=( Q,刀,S , q, qi)等價(jià)的 NFA M 3=( Q,刀,S 2, q, qi)其中對于 一 (q,a)eCT 刀 S2(q,a)=SJ(q,a)然后按照以前學(xué)過的方法構(gòu)造與NFA M

12、 3=( Q, E ,S 2, q, qi)等價(jià)的DFAMi=(Qi,E,S i,qo,Fi)其中:Qi=2Q Fi= qoisi(qi,q2,，qn,a)=pi,p2,pn當(dāng)且僅當(dāng) S2(q i,q2 ,，qn,a)= p i,p2,pn *AA注：此題(io題)張友坤、吳玉涵所做完全一樣！iO、構(gòu)造識別下列語言的NFA(吳玉涵02282091)(i) x x 0,i +且x中不含形如00的子串(2) X x0,1且x中含形如10110的子串(3) xxA0,1 +且x中不含形如10110的子串0. 10. 1(4) X A0,r和X的倒數(shù)第10個(gè)字符是X且以01結(jié)尾(5) x xA0,1

13、+且x以0開頭以1結(jié)0, 101(6) x xA0,1 +且x中至少含有兩個(gè)10. 10. 10. 1xxA0,1但如果x以1結(jié)尾，則它的長度為偶數(shù)；如果以0結(jié)尾，則它的長度為奇數(shù)1(8) xxA0,1+且X的首字符和尾字符相等0. 11(9) xcoxTx,/k0,11這是最基本的單元，其他的可以通過這個(gè)逐級構(gòu)造岀來，以滿足題目要求。it*11.等價(jià)的DFA.根據(jù)給定的NFA,構(gòu)造與之(吳丹 02282090)(1) NFAMi的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)qoqO,q1q0,q2q0,q2qiq3,q00q2q20q3,q1q2,q1終止?fàn)顟B(tài)q3q3,q2q3q

14、0解答:狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0qO,q1q0,q2q0,q2qO,q1q0,q1,q3q0,q2q0,q2q0,q2qo,qiq0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2終止?fàn)顟B(tài)q0,q1,q3q0,q1,q2,q3qO, q2,q3q0,q1,q2終止?fàn)顟B(tài)q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0, q2終止?fàn)顟B(tài)q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2qO,q1 qo,qi,q3 q0,q2,q310122o011,2 廠、0,12 3,q,F3),

15、其中Qa =2QI,F3 = PI3P2.Pm |pi, P2.PmQ, Pi , P.Pm Fi =,、3(qi.qn,a)ziPiPm=、i (q.qn, a)r. Pi.Pm在此基礎(chǔ)上 M2，Q2 =Q3j 2= 3jF2 = PiPm |Pi Prn F3 二即取所有Mi確定化后不是終結(jié)狀態(tài)的狀態(tài)為M?的終結(jié)狀態(tài)。為了證明L(M2)二a *丄(M3),我們在M3的基礎(chǔ)上M4= (Q4,；4,q,F4),其中Q4二Q3,、： 4= , F4 = Q4,即所有Mi確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然L(M4)八XL(M2),則、(q,x)F“二(q,x) F3廠二XL(M3),又因?yàn)?q0,x

16、) Q3二(q,x) F4二、(q,x)L(M r,故 x、*-L(M3),故L(M2)丄M)同理容易證明L(M2) = 7 (f r；),x2)-，(q02 * X2J= 202 *2)7即得證xL(M)2)再證明L(M) L(M!)L(M2)設(shè)xL(M),即、(qi,x) =f2由于M是從qi啟動的，由M的定義可知,M要達(dá)到狀態(tài)怯必須 先到由于除了對應(yīng)狀態(tài)轉(zhuǎn)移函數(shù)式;(fiJ = q02的移動夕卜，不存 在從仏出發(fā)的任何其他移動，而且該移動是的必經(jīng) 移動,所以， 比存在X的前綴Xi和后綴X2,使得咲議2,并且Xi將M從狀態(tài)qoi引導(dǎo) 到狀態(tài)fi,x?將M從狀態(tài)q02引導(dǎo)到狀態(tài)f2即、(qo

17、,x)二、1,皿)=s(fi,X2)冷)=6 (q x )這表明xL(M JX4(M2)從而 x = XjX2 L(M OL(M 2)故 L(M) L(Mi)L(M2)綜上所述，L(MaL(Mi)L(M2if*(吳丹 02282090)18證明:對于任意的 FAML(QJZ； ,qoi,),FA M2=( Qzg 2,2002,& ) 存在 FAM,使得 LM= LMa|LM2o證明：不妨將這些FA看成DFA取M 二 Q1 Q29 c, r, qoi, q。？ , F對于-a : 工 H2, q, P 盧 Q,、q,p , a= nq, a ,學(xué) p, a .1 設(shè)：x L M 貝I x=x1

18、x2xk 其中 xi i1,ki_ 二 Pr2使得q,p, xi = Tq, xi A 2 P, xi.xi LMi riLMzhX LMjILM?從而可得L M L Mi Dl M22 設(shè)：x L Mi IT M2 貝 vx =x1x2xk其中 xi i 1,k l二 I有q, xi且：2P, xi從而使得、1 q, xi Iqp, xi ；2p, xiq,p 1, xixi L M = x L M從而可得LM1PILM2LM綜合(2)可得LM= L MjlL M2 O又因?yàn)镕A和DFA具有等價(jià)性，所以原命題得證。19、總結(jié)本章定義的所有FA,歸納出它們的特點(diǎn)，指出它們之間的差別。(吳玉涵0

19、2282091)本章學(xué)習(xí)了 DFA, NFA, NFA, 2DFA和2NFA所有的FA都是一個(gè)五元組(Q, 2, S, q0, F)最大的區(qū)別就是狀態(tài)轉(zhuǎn)移函數(shù)S對于DFA,字母表中的每個(gè)字母都有唯一確定的狀態(tài)轉(zhuǎn)移函數(shù)。也就是說X2, q Q, a2只有唯一確定的狀態(tài)。一 3(q,a)Q對于NFA,對于字母表中的每個(gè)輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對于身的移動。串，是一個(gè)到自對于NFA,是指在不接受任何字符的情況下，自動機(jī)的狀態(tài)可以發(fā)身轉(zhuǎn)移。對于2DFA ,對于字母表屮的每個(gè)字符，對于每個(gè)狀態(tài)都有唯一的狀態(tài)轉(zhuǎn)移，即- 3 (q, a) Q X2, q Q, a2只有唯一確定的狀態(tài)。與DFA不同的是

20、，2DFA的讀頭可以在一次 狀態(tài)轉(zhuǎn)移中不移動，或者回退一個(gè)，或者向下讀一個(gè)。對于2NFA ,與2DFA相似，但是并不是對于字母表屮的每個(gè)輸入字符都有轉(zhuǎn)移函數(shù)，2NFA與2DFA的區(qū)別類似于DFA與NFA的區(qū)別。20構(gòu)造如圖320所個(gè)的DFA對應(yīng)的右線性文法。(周期律02282067)對圖1：構(gòu)造文法G= (V, T, P, S),其中V=S, A, B, C, T=1 , 0S0A|1|1CA0S|1|1CP：B0|0C |1SC0A|1A對圖2:構(gòu)造文法G= (V, T, P, S),其屮V=S, A, B, C, T=1 , 0S0A|1BA 1S|1|0BP：B0C |0|1AC0A|1

21、A*祜 *祜 *襯*襯 *桂*桂*吳賢毘02282047)21 .構(gòu)造下圖所示DFA對應(yīng)的左線性文法。圖形如下所示解：設(shè)q。、 由于q2 為不可 達(dá)狀 態(tài)，故 先去掉 該狀 態(tài)。S A1 | B1 10q2q3q 1、q2、q3所對應(yīng)的字符分別為A、B、G得到該圖所對應(yīng)的左線性文法為:4 G0| G1 AO 0LBO圖形如下所示:1設(shè)該狀C、Do解：圖屮有多個(gè)終結(jié)狀態(tài)，為方便起見，增加一個(gè)終結(jié)狀態(tài)（紅色表示）態(tài)所對 應(yīng)的字符為G又設(shè)q、q2、q3所對應(yīng)的字符分別為人則該圖所對應(yīng)的左 線性文法為：A C0| BO | &“ COSBO| A1 1 B C1 DO | D1 AO | 0AT B1

22、22. 根據(jù)（敖雪峰02282068）下列給定文法，構(gòu)造相應(yīng)的FA(1)文法G1的產(chǎn)生式集合如下:G1: ST a|AaA T a|Aa|cA|BbA T a|Aa|Ac|BbBTa|b|c|Ba|Bb|Bc解答：文法G1對應(yīng)的FA如下所示Bz a,b,c 丿文法G2對應(yīng)的必如下所示a,b,c(馮蕊 02282075)23. FA M的移動函數(shù)定義如下3 (qo,3)=q 03(q,1)=q 13q,0)=q 23qi,1)=q 33(q2,0)=q 23(q3,i)=q 3其中,q2,q3為終態(tài).M是DFA嗎？為什么？不是，因?yàn)椴⒉皇撬械臓顟B(tài)(2)畫出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖在接收一個(gè)字對

23、農(nóng)屮的字符時(shí)會有一個(gè)狀態(tài)與乙對應(yīng)qi3101/(qOl33、0、0,3 1-1(qOBOV一 11,30,1,3給出你所畫出的 DFA的每個(gè)狀態(tài)q的set(q):set(q)=x|x 工且3 (q,x)=q set(qo)=3 set(qi)=3 1set(q2)= 3*100*set(q3)= 3*111*set(q)=( 3 0|3 13|3 100 (113)|3 111 a的產(chǎn)生式，增加一個(gè)開始狀態(tài)乙使得q。二Z所以E=F,對于產(chǎn)生式B、Aa,則有、(A,a)=B,對于產(chǎn)生式：B a,且E是開始狀態(tài)，則有、：(E,a)二B.下面證明G(E)與FA等價(jià)，即證明L(G(E)=L(M)不會:

24、)2)根據(jù)FA M =(Q；,、，q0,F),構(gòu)造相應(yīng)的G(E)為了方便起見，在根據(jù)給定的FA構(gòu)造等價(jià)的左線性文法的之前，先對 FA做如下的處理：1. 刪除FA的陷阱狀態(tài)。2. 在FA中增加一個(gè)識別狀態(tài)3. “復(fù)制” 一條原來到達(dá)終止?fàn)顟B(tài)的弧，使它從原來的起點(diǎn)出發(fā)，到達(dá)新添 加的 識別狀態(tài)。相應(yīng)的文法的構(gòu)造依照如下兩條進(jìn)行：1. 如果、:(A,a)Zl B,則有產(chǎn)生式Ba2. 如果且A是開始狀態(tài)qa，則有產(chǎn)生式B a。*?|O|C*J|O|O|C*3|O|O|O|C*3|O|O|C* 林*林* 林* 林 *林(吳丹 02282090)26. 證明定理3-6o ( 2DFA與FA等價(jià))證明：對于

25、2DFAM是一個(gè)五元組M二Q, ,:, q. , F其中，Q, , q。，F(xiàn)的意義同與DFAo、： Q :二一；QL, R, S?,對于一 q, a 三 Q1如果心(q, a二!p, L/表示在讀入a從狀態(tài)q轉(zhuǎn)移到狀態(tài)p,并將 讀頭向左移動，指 向輸入字符的前一個(gè)字符。2如果心(q, a二：p, R 表示在讀入a從狀態(tài)q轉(zhuǎn)移到狀態(tài)p,并將 讀頭向右移動，指 向輸入字符的下一個(gè)字符。3如果心(q, a二Ip, 9表示在讀入a從狀態(tài)q轉(zhuǎn)移到狀態(tài)p,讀頭 保持在原位置不 動。我們構(gòu)造與之等價(jià)的FA27. 證明定理3-7(周期律02282067)證明：因?yàn)镕A是一-種特殊的2NFA,他是當(dāng)qQ,a7時(shí)

26、，都有、；(q,a) = ( D)(Pm,D)，此時(shí)的D只為往右移動，即一個(gè)每一個(gè)狀態(tài)讀入一個(gè)字符后讀頭都往右移動指向下一字符的2NFA,故對任意的FA,定會找到一個(gè)與之等 價(jià)的2NFA與之對應(yīng)。因此我們只需要證明對任何的2NFA M 1 =(Q.,： r, Fi,q。)，都存在FAM 2= (Q2/2, F2, q。)與之等價(jià)。對于任何的 2NFA Mi =(Qi, 、. “ Fi, q。)，構(gòu)造 FA M2 =(Q2，、2,F2,q。),按三個(gè)方式構(gòu)造：2：1 如果 q Qa ,、i(q,a)二p, R,則、2(q,a)二 p ；2如果 q Qi,a : -二、i(q,a)zi p,S,則如果、i(p,a匚o, R,則、2(q,a) =0 ；如果r ( p, a) =o, S,則重復(fù)第二步；如果r(p,a) o, L,則對于集合 A = r|b、j(r,b) = (o,R),、2(q,a)二 r,r