形式語言與自動機理論

第三章作業(yè)答案1.已知DFAM1與M2如圖3—18所示。(敖雪峰02282068)請分別給出它們在處理字符串1011001的過程中經(jīng)過的狀態(tài)序列。請給出它們的形式描述。S0S0圖3—18兩個不同的DFA解答：(1)M1在處理1011001的過程中經(jīng)過的狀態(tài)序列為q0q3q1q3q2q3q1q3;M2在處理1011001的過程中經(jīng)過的狀態(tài)序列為q0q2q3q1q3q2q3q1;(2)考慮到用形式語言表示，用自然語言似乎不是那么容易，所以用圖上作業(yè)法把它們用正則表達式來描述：M1:[01+(00+1)(11+0)][11+(10+0)(11+0)]*M2:(01+1+000){(01)*+[(001+11)(01+1+000)]*}個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個2.構(gòu)造下列語言的DFA(1)(陶文婧02282085)(2){0,1}*0,1{0，1}+(2.構(gòu)造下列語言的DFA(1)(陶文婧02282085)(2){0,1}*0,1{0，1}+S（4）{xlxe{0,1}*且x中不含00的串}（可接受空字符串，所以初始狀態(tài)也是接受狀態(tài)）SSS1（5）{xlxe{0，1}+且x中含形如10110的子串}0（6）{xlxe{0，1}+且x中不含形如10110的子串}（設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進入陷阱狀態(tài)）1（7）{xlxe{0，1}+且當(dāng)把x看成二進制時，x模5和3同余，要求當(dāng)x為0時，鳳=1,且x^0時，x的首字符為1}1.以0開頭的串不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)DFA在啟動狀態(tài)讀入的符號為0，則進入陷阱狀態(tài)2.設(shè)置7個狀態(tài)：開始狀態(tài)qs,q0.除以5余0的等價類，％除以5余1的等價類,q2.除以5余2的等價類，q3.除以5余3的等價類，q4.除以5余4的等價類，接受狀態(tài)qt（8）（xlxe{0,1}+且x的第十個字符為1}（設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個字符為0,進入陷阱狀態(tài)）廠、廠、廠、s廠、cST山馬叫馬04馬vvUAJ（9）{xlxe{0，1}+且x以0開頭以1結(jié)尾}（設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€字符為1時，進入陷阱狀態(tài)）SS（10）{xlxe{0，1}+且x中至少含有兩個1}則它的長度（11）{xlxe{0,1}+且如果x以1結(jié)尾，則它的長度為偶數(shù)；如果x以0結(jié)尾，為奇數(shù)}可將{0，1}+的字符串分為4個等價類。則它的長度q0國的等價類，對應(yīng)的狀態(tài)為終止?fàn)顟B(tài)q1：x的長度為奇且以0結(jié)尾的等價類q2x的長度為奇且以1結(jié)尾的等價類q3：x的長度為偶且以0結(jié)尾的等價類q4：x的長度為偶且以1結(jié)尾的等價類S（12）{xlx是十進制非負數(shù)}5，6，7，8，9（13）中S（14）￡S&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個

(張友坤02282061)3⑴10Z={o,i}Set(q0)={xIxGZ*}(2)Z={o,i}S（12）{xlx是十進制非負數(shù)}5，6，7，8，9（13）中S（14）￡S&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個(張友坤02282061)3⑴10Z={o,i}Set(q0)={xIxGZ*}(2)Z={o,i}Set(q0)=eSet(ql)={xIxGZ+}(3)Z={o,i}Set(q0)=eSet(ql)={xIxeZ+并且x中不含形如00的子串}Set(q2)={xIxeZ+并且x中不含形如00的子串}⑷nZ={O,1}Set(q0)=(xSet(ql)={x11xexeZ*,并且x6｛0｝*或者x中含形如100的子串｝Z*,并且X中含形如1的子串｝Set(q2)={x1xeZ*,并且x中含形如10的子串｝Set(q3)={x1xeZ*,并且x中含形如101的子串｝Set(q4)={x1xeZ*,并且x中含形如1011的子串｝Set(q5)=(x1xeZ*,并且x中含形如10110的子串｝(6)Z={O,1}Set(qO)={S)Set(ql)=(xIxg{0+}}Set(q2)={xIxeZ*,并且x中不含形如10110的子串而且x中含有1}Set(q3)={xIxeZ*,并且x中不含形如10110的子串而且x中含有1}(7)0Z={o,i}Set(qs)={8}Set(qe)={0}Set(ql)=(xIx€Z+,并且把x看成二進制數(shù)時，x%5=1)Set(q2)={xIxeZ+,并且把x看成二進制數(shù)時，x%5=2}Set(q3)={xIxeE+,并且把x看成二進制數(shù)時，x%5=3}Set(q4)={xIxeZ+,并且把x看成二進制數(shù)時，x%5=4}Set(q0)={xIxeE+,并且把x看成二進制數(shù)時，x%5=0并且x不為0}(8)M={Q,E,§,q0,F}。={%月1月2，??％}E={0,1}當(dāng)0<=i<=8時候，§(q「0)=§(qi^Fi+D§(q9,1)=q10§(q1o，0)=§(q10,1)=q10F={q10}Set(q0)={8}Set(q1)={0,1}Set(q2)={x|xeE+,并且1x1=2}Set(q3)={x|xeE+,并且1x1=3}Set(q4)={x|xeE+,并且1x1=4}Set(q5)={x|xeE+,并且|x|=5}Set(q6)={x|xeE+,并且|x|=6}Set(q7)={x|xeE+,并且|x|=7}Set(q8)={x|xeE+,并且|x|=8}Set(q9)={x|xeE+,并且|x|=9}Set(q10)={x|xeE+,并且x的第十個字符是1}⑼M={Q,E,§,q0,F}Q={q0,q1,q2}E={0,1}§(q0,0)=q1§(q1,0)=q1§(q1,1)=q2§(q2，1)=q2§(q2，0)=q1F={q?}Set(q0)={8}Set(q1)={x|xeE+,并且x以0開頭以0結(jié)尾}Set(q2)={x|xeE+,并且x以0開頭以1結(jié)尾}(10)M={Q,E,§,q0,F}Q={q0,q1,q2}E={0,1}§(q0,0)=q0§(q0,1)=q1§(q1,0)=q18(qi」)=q28(q拱片q28(q2,0)=q2F={q2)Set(q0)={0}*Set(q1)={xIxeE+,并且x中只有一個1}Set(q2)={xIxeZ+,并且x至少有倆個1}M={Q,1,8,q0,F}Q={q0,q1,q2,q3,q4}E={0,1}8(q0,0)=q18(q0,1)=q48(q1,0)=q38(q1,1)=q28(q2,1)=q48(q2,0)=q18(q3,0)=q18(q3,1)=q48(q4,1)=q28(q4,0)=q3F={q0,q1,q2}Set(q0)={8}Set(q1)={x|xeE+,以0結(jié)尾，長度為奇數(shù)}Set(q2)={x|xeE+,以1結(jié)尾，長度為偶數(shù)}Set(q3)={x|xeE+,以0結(jié)尾，長度為偶數(shù)}Set(q4)={x|xeE+,以1結(jié)尾，長度為奇數(shù)}(12)M={Q,E,8,q0,F}Q={q0,q1,q2,q3,q4}E={.,0,1,2,...,9}F={q1,q2,q4}8(q0,0)=q18(q0,1|2|3|4|5|6|7|8|9)=q28(q1,.)=q28(q2,0|1|2|3|4|5|6|7|8|9)=q28(q2,.)=q38(q3,0|1|2|3|4|5|6|7|8|9)=q48(q4,0|1|2|3|4|5|6|7|8|9)=q4Set(q0)={8}Set(q1)={0}Set(q2)={十進制正整數(shù)}Set(q3)={十進制非負整數(shù)后面接個小數(shù)點.}Set(q4)={十進制正小數(shù)}(13)Set(q0)={8}Set(q0)=0(14)Set(q0)={8}個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個4在例3-6中，狀態(tài)采用q［aa...a］的形式，它比較清楚地表達出該狀態(tài)所對應(yīng)的記憶內(nèi)12n容，給我們解決此問題帶來了很大的方便，我們是否可以直接用［%a2...?！ǎ荽鎞［aa...a］呢？如果能，為什么？如果不能，又是為什么？從此問題的討論，你能總12n結(jié)出什么來？(唐明珠02282084)答：我認為能夠直接用［aa...a］代替q［aa...a］，因為在例3-6中，q［aa...a］只是一12n12n12n種新的表示方法，用來表示狀態(tài)存儲的字符，這樣就省去了在8中逐一給出每一個具體的輸入字符和狀態(tài)的定義。它的作用在于使FA中狀態(tài)定義更加簡潔。得到結(jié)論：在今后描述FA時，應(yīng)該根據(jù)具體的情況，使用適當(dāng)?shù)姆椒ā?******************************************************************************試區(qū)別FA中的陷阱狀態(tài)和不可達狀態(tài)。(吳賢珺02282047)解：⑴陷阱狀態(tài)(課本97頁)：指在其它狀態(tài)下發(fā)現(xiàn)輸入串不可能是該FA所識別的句子時所進入的狀態(tài)。FA一旦進入該狀態(tài)，就無法離開，并在此狀態(tài)下，讀完輸入串中剩余的字符。⑵不可達狀態(tài)(課本108頁)：指從FA的開始狀態(tài)出發(fā)，不可能到達的狀態(tài)。就FA的狀態(tài)轉(zhuǎn)移圖來說，就是不存在從開始狀態(tài)對應(yīng)的頂點出發(fā)，到達該狀態(tài)對應(yīng)頂點的路徑。⑶從兩者的定義可見：相對于不可達狀態(tài)來說，陷阱狀態(tài)是可達的。但是，它們都是狀態(tài)轉(zhuǎn)移圖中的非正常狀態(tài)。如果從狀態(tài)轉(zhuǎn)移圖中的狀態(tài)引一條弧到不可達狀態(tài)，同時不可達狀態(tài)所有的移動都是到自身。這樣，不可達狀態(tài)就變成了陷阱狀態(tài)。力$$$$$$$$$$$$$$$$$力、******************************************************************************注：此題目有問題，可以將題設(shè)改為：X中0和1個數(shù)相等且交替出現(xiàn)證明：題目有不嚴(yán)密之處，圖中給出DFA與題目中的語言L(M)={x|xx』0，1}+且x中0的個數(shù)和1的個數(shù)相等}不完全對應(yīng)，首先圖中的DFA可接受空字符串，而L(M)不接受，其次，對于有些句子，例如1100，L(M)可以接受，但DFA不接受根據(jù)圖中的DFA可看出，右下角的狀態(tài)為陷阱狀態(tài)，所以去除陷阱狀態(tài)由DFA可構(gòu)造出與其對應(yīng)的右線性文法：(劉鈺02282083)ST0AAT1S11ST1BBT0S10將1S,1代入5T0A；0S,0代入5T1B得ST01S101ST10S110由此可以看出該文法接受的語言為L={(10I01)*},顯然01或10分別是作為整體出現(xiàn)的，所以L(M)中0和1的個數(shù)相等?！啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊?*****************************************************************************設(shè)DFAM=(0E,5,q0,F)，證明：對于Vx,ye^*,qeQ,5(q,xy)=8(6(q,x),y)注：采用歸納證明的思路證明：(周期律02282067)首先對y歸納，對任意x來說，IyI=0時，即y=e根據(jù)DFA定義6(q,S)=q,6(q,xy)=6(q,x)=6(6(q,x),8)=6(6(q,x),y)做原式成立。當(dāng)IyI=n時，假設(shè)原式成立，故當(dāng)IyI=n+1時，不妨設(shè)y=wa,IwI=n,IaI=1根據(jù)DFA定義6(q,xa)=6(6(q,x),a),ae￡，故6(q,xy)=6(q,xwa)=6(6(q,xw),a)=6(6(6(q,x),w),a)=6(6(q,x),wa)=6(6(q,x),y)原式成立，同理可證，對任意的y來說，結(jié)論也是成立的。綜上所述，原式得證“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************證明:對于任意的DFAM1=(Q,￡,&,q0,F1)存在DFAM2=(Q,￡,&,q0,F2),(馮蕊02282075)使得L(M2)=￡*—L(MJ。證明：(1)構(gòu)造m2。設(shè)DFAM1=(Q,￡,5,q0,F1)取DFAM2=(Q,￡,5,q0,Q—F1)(2)證明L(M2)=￡*—L(M1)對任意xe￡*xeL(M2)=￡*—L(M1)05(q,x)eQ—F]05(q,x)eQ并且5(q,x)wF]0xe￡*并且xwL(M]Qxe￡*—L(M1)“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************對于任意的DFAM]_(Q],E,51,q01,F1),請構(gòu)造DFAM1=(Q2,E,52,q02,F2)，使得L(M])=L(M2)t。其中L(M)t={xIxtEL(M)}(褚穎娜02282072)(1)構(gòu)造8-NFAM使得L(M)=L(M1)取8-NFAM=(Q,E,5,q0,{q01})其中：1)Q=Q1U{q0},q0wQ12)對于Vq,p￡Qi,aeE,如果51(q,a)=p,qE5(p,a)3)5(qo,￡)=Fi證明：L(M)=L(M1)T對Vx=a1a2...amEL(M)q°ai%...amEaia2...amES支…amE%42-?amI■…E%%-&卜ai%???%q01其中qfE5(q0,頃qi^5(qf,ajq2^5(qi,a2),.qoie5(qm-i,am)并且qfGFI則5i(q°i，am)=qm-i，5i(qm-i，am-i)=4皿-2，???5iW，%)=S5i%諾=4f因此qoiamam-i-aiIamqm-i弟…K%日2%%K%..%"iIamam-i...%aiqf因此amam-i...aiEL(Mi)即xtGL(Mi)同理可證對于Vx=aia2.amEL(Mi)xT=amami.ai^L(Mi)L(M)=L(M])t得證將￡-NFAM確定化首先構(gòu)造與￡-NFAM=(Q，E，5,qo，(q0i})等價的NFAM3=(Q，E，52，q0，(q0i})其中對于V(q,a)EQ*工52(q,a)=5人(q,a)然后按照以前學(xué)過的方法構(gòu)造與NFAM3=(Q,E,52,q0,{q0i})等價的DFAMi=(Qi,E,5i,[q0],Fi)其中：Q]=2qFi={q0i}5i([qi,q2,.,qn],a)=[pi,p2,.,pn]當(dāng)且僅當(dāng)52({qi,q2,.,qn},a)={pi,p2,.,pn}*******************************************************************************注：此題(10題)張友坤、吳玉涵所做完全一樣！！i0、構(gòu)造識別下列語言的NFA(吳玉涵0228209i)(i){x|xe{0,i}+且尤中不含形如00的子串}ii

(2){xxe{0,1}+且尤中含形如10110的子串}0,1⑶{xxe{0,1}+且尤中不含形如10110的子串}{xxe{0,1}+和尤的倒數(shù)第10個字符是1,且以01結(jié)尾}0,1J—10，10，10，1

oooo0，1100101010”'{xxe{0,1}+且尤以0開頭以1結(jié)尾}(6){xxe{0,1}+且尤中至少含有兩個1}0，10，10，1(7){xxe{0,1}*且如果尤以1結(jié)尾，則它的長度為偶數(shù);如果以0結(jié)尾，則它的長度為奇數(shù)}

（8）{xxe{0,1}+且尤的首字符和尾字符相等}(9){仙xtx,①e{0,1}+}0,10,1這是最基本的單元，其他的可以通過這個逐級構(gòu)造出來，以滿足題目要求。個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個11.根據(jù)給定的NFA，構(gòu)造與之等價的DFA,（吳丹02282090）（1）NFAM的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0{q0,q1}{q0,q2}{q0,q2}q1{q3,q0}0{q2}q20{q3,q1}{q2,q1}終止?fàn)顟B(tài)q3{q3,q2}{q3}{q0}

解答:狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0[q0,q1][q0,q2][q0,q2][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q1,q2,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,q3][q0,q1,q2]終止?fàn)顟B(tài)[q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q1,q2]終止?fàn)顟B(tài)[q0,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q2]終止?fàn)顟B(tài)[q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]q00?:?120,41,220,1[q0,q2]1,q2]2q00?:?120,41,220,1[q0,q2]1,q2]2100,1[q0,q1,q2,q3]?2圖3-9所示NFA等價的DFA(2)NFAM2的狀態(tài)轉(zhuǎn)移函數(shù)如表3-10狀態(tài)說明-狀態(tài)輸入字符012開始狀態(tài)q0{q1,q3}{q1}{q0}q1{q2}{q1,q2}{q1}q2{q3,q2}{q0}{q2}終止?fàn)顟B(tài)q3{q0}{q3}解答:狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0[q1,q3][q1][q0][q1,q3][q2][q0,q1,q2][q1,q3]

[q1][q2][q1,q2][q1][q2][q2,q3][q0][q2][q0,q1,q2][q1,q2,q3][q0,q1,q2][q0,q1,q2][q1,q2][q2,q3][q0,q1,q2][q1,q2]終止?fàn)顟B(tài)[q2,q3][q2,q3][q0][q2,q3]終止?fàn)顟B(tài)[q1,q2,q3][q2,q3][q0,q1,q2][q1,q2,q3][q0,q1,q2][q1,q3]212100[q2]20「[q2,q3]011[q1]'、.1?J002[q3,q1,q2]20圖3-10所示NFA等價的DFAe力力力$$$$$$$$$$$$$$$$$力、mi，+++++++++++++個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個12.證明對于任意的NFA,存在與之等價的NFA,該NFA最多只有一個終止?fàn)顟B(tài)(劉鈺02282083)證明：對于任意的NFAM=(Q,E,S,q0,F)，我們?nèi)绻軜?gòu)造出一個只有一個終止?fàn)顟B(tài)的NFA,并且與之等價，即可證明上面的定理而對于任意的NFA存在下面兩種情況：終止?fàn)顟B(tài)只有一個終止?fàn)顟B(tài)有多個要構(gòu)造這個等價的NFA,可以采用如下方法：對(1)無需變化，該NFA即為滿足條件的NFA對(2)可以在該NFA的狀態(tài)圖上添加一個新的終止?fàn)顟B(tài)，并將原來的多個終止?fàn)顟B(tài)所連接的弧復(fù)制到該狀態(tài)上，此時這個終止?fàn)顟B(tài)為新狀態(tài)圖中唯一的終止?fàn)顟B(tài)，且這個新的NFA與原NFA等價，滿足條件我們總能構(gòu)造出這樣的NFA因此對于任意的NFA，存在與之等價的NFA,該NFA最多只有一個終止?fàn)顟B(tài)&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個13.試給出一個構(gòu)造方法，對于任意的NFAM=(Q,Z,5,q,F)，構(gòu)造NFA11101M=(Q,Z,5,q,F)，使得L(M)=Z*-L(M)2220221注：轉(zhuǎn)化成相應(yīng)的DFA進行處理，然后可參考第8題的思路

證明:(周期律02282067)首先構(gòu)造一個與NFA吃等價的DFA,吃根據(jù)定理3.1(P106),頃「"(吃)構(gòu)造M=(Q,Z,5,[q],F),其中33303Q=2Q1，F(xiàn)={[證明:(周期律02282067)首先構(gòu)造一個與NFA吃等價的DFA,吃根據(jù)定理3.1(P106),頃「"(吃)構(gòu)造M=(Q,Z,5,[q],F),其中33303Q=2Q1，F(xiàn)={[p,p...p]I{p,p...p}cQ,{p,p...p}nF林},{p,p...p}cQ,a”3312m12m12m112m5([q...q],a)=[p...p]。5({q...q},a)={p...p}

31n1m11n1m在此基礎(chǔ)上M，Q=Q,5=5,F={[p...p]I[p...p]nFM}2232321m1m3即取所有M1確定化后不是終結(jié)狀態(tài)的狀態(tài)為M2的終結(jié)狀態(tài)。為了證明L(M)二￡*-L(M)，我們在M的基礎(chǔ)上M=(Q,Z,5,q,F)，其23344404中Q4=Q3,54="F4=Q4，即所有M1確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然L(M4)=￡*,n5(q0,x)PlF3w?nx冬L(M3),又因5(q,x)eQn5(q,x)eFn5(q,x)eL(M)=￡*,故xe￡*-L(M)，VxeL(M2),則5(q0,XF2州-L(M3)同理容易證明L(M2)目￡-L(M3)故L(M2)=￡*-L(M3)可知，構(gòu)造的M2是符合要求的?！啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊?******************************************************************************14.構(gòu)造識別下列語言的8-NFA。(吳賢珺02282047)⑴{x|xE{0,1}+且x中含形如10110的子串}U{x|xE{0,1}+和x的倒數(shù)第10個字符是1，且以01結(jié)尾}。解：得到的e-NFA如下所示：eS⑵{x|xE{0,1}+且x中含形如10110的子串}{x|xE{0,1}+和x的倒數(shù)第10個字符是1,且以01結(jié)尾}解：得到的e-NFA如下所示：S0,1—O⑶{x|xE{0,1}+且x中不含形如10110的子串}U{x|xE{0,1}+且x以0開頭以1結(jié)尾}。S0,1—O解：關(guān)鍵是構(gòu)造第一個FA，方法是設(shè)置5個狀態(tài)：q0：表示開始狀態(tài)，以及連續(xù)出現(xiàn)了兩個以上的0時所進入的狀態(tài)。q1：表示q0狀態(tài)下接受到1時（即開始狀態(tài)或2個以上的0后輸入1時）所進入的狀態(tài)。q2：表示％狀態(tài)下接受到0時（即開始狀態(tài)或2個以上的0后輸入10時）所進入的狀態(tài)。q3：表示q2狀態(tài)下接受到1時（即開始狀態(tài)或2個以上的0后輸入101時）所進入的狀態(tài)。q4：表示q3狀態(tài)下接受到1時（即開始狀態(tài)或2個以上的0后輸入1011時）所進入的狀態(tài)。故得到的e-NFA如下所示：

⑷{x|xE{0,1}+且x中不含形如00的子串}{x|xE{0,1}+且x中不含形如11的子串}。解：得到的e-NFA如下所示：另外，本題可以構(gòu)造DFA如下（其中qt為陷阱狀態(tài)）:

⑸{x|xE{0,1}+且x中不含形如00的子串}C{x|xE{0,1}+且x中不含形如11的子串}。解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相間的串。所以，得到的8-NFA如下所示:另外，本題可以構(gòu)造DFA如下(其中q+為陷阱狀態(tài)):個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個15.(1)根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù)，起始狀態(tài)q0的￡閉包為^-CLOSURE(q0)={q0q2}。由此對以后每輸入一個字符后得到的新狀態(tài)再做￡閉包，得到下表：(陶文婧02282085)狀態(tài)01{q0q2}{q0q】q2}{q0q1q2q3}{q0q1q2}{q0q1q2q3}{q0q】q2q3}{q0q,q2q3}{q0q]q2q3}{q0q】q2q3}q0={q0q2}，q1={q0q1q2}，q2={q0q1q2q3}，因為q3為終止?fàn)顟B(tài)，所以q2={q0q1q2q3}為終止?fàn)顟B(tài)’’’’’’’’Sq(0&

（2）又上述方法得Sq(0&狀態(tài)01{q】q3}{q3q2}{q0q,q2q3}{q3q2}{q3q2}{q0q]q3}{q0q1q2q3}{q1q2q3}{q0q1q2q3}{q0q1q3}{q1q2q3}{q0q1q2q3}{q1q2q3}{q3q2}{q0q1q2q3}q°={q1q3}，q『{q3q2}，q2={q0^iq2q3}，q3={q0^iq3}，q4={qiq2q3}因為各狀態(tài)均含有終止?fàn)顟B(tài)，所以q0,q1，q2，q3,q4均為終止?fàn)顟B(tài)’’’’S注：本題沒有必要按照NFA到DFA轉(zhuǎn)化的方法來做，而且從s-NFA到NFA轉(zhuǎn)化時狀態(tài)沒有必要改變，可以完全采用s-NFA中的狀態(tài)如⑴S狀態(tài)0iq0（開始狀態(tài)）{qoq.%qJ{氣&,%,q3}q.{qoq.%qJ{q.q。qJq2{qoq.%q』{q.q2qJq3（終止?fàn)顟B(tài)）{qo,&,氣,qJ{qo,qi,q。,qJ⑵狀態(tài)o1qo（開始狀態(tài)）{q.q2q3}{qoqiq。q』_q{q「"{q.q「-q2{q。qJ1，2{qoq2qJq3（終止?fàn)顟B(tài)）,L,3空O,2,3_i^d&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個16.證明對于V的FAM1=(Q1,E1,81,q01,F1)，F(xiàn)AM1=(Q2,E2,82,q02,F2)，存在FAM，使得L(M)=L(M1)UL(M2)(褚穎娜02282072)證明：不妨設(shè)Q1與Q2的交集為空(1)構(gòu)造M=(Q1UQ2U{q°},；8,q0，F(xiàn))其中：e=e1ue2f=f1uf26(q0,e)={q0i,q02}對于VqGQ1,aeE18(q,a)=5i(q,a)對于Vq￡Q2,a￡E2,6(q,a)=62(q,a)(3)證明：1)首先證L(M1)UL(M2)EL(M)設(shè)xGL(M1)UL(M2)，從而有xEL(M])或者xEL(M2),當(dāng)xGL(M1)時61(qo1,x)GF1由M的定義可得：6(q0,x)=6(qo,ex)=6(6(qo,e),x)=6({q01,q02},x)=6(q01,x)U6(q02,x)=61(q01,x)U6(q01,x)EF]U6(q01,x)即xEL(M)同理可證當(dāng)xEL(M2)時xEL(M)故L(M])UL(M2)EL(M)2)再證明L(M)EL(M])UL(M2)設(shè)xEL(M)則6(q0,x)EF由M的定義：6(q0，x)=6(q0,ex)=6(6(q0,e),x)=6({q01,q02}，x)=6(q01,x)U6(q02,x)如果是6(q01,x)因為Q1與Q2的交集為空而且6(q0,x)GFF=F1UF2貝6(q01,x)=61(q01,x)GF1因此x￡L(M1)如果是6(q02,x)因為Q1與Q2的交集為空而且6(q0,x)GFF=F1UF2貝6(q02,x)=62(q02,x)GF1因此x￡L(M2)因此xEL(M1)UL(M2)L(M)EL(M1)UL(M2)得證因此L(M)=L(M1)UL(M2)“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************(唐明珠02282084)17證明：對于任意的FAM=(Q,￡,8,q,F),FAM=(Q,￡,8,q,F),11110112222022存在FAM,使得L(M)=L(M1)L(M2).證明：令M=(Q1Q2,Z,8,q01,{f2}),其中6的定義為：1)對VqEQj-ifJ,a￡EU{e}8(q,a)=81(q,a)；對VqEQ2-{f2}，a￡EU{￡}8(q,a)=82(q,a)；8(f1，￡)={q02}要證L(M)=L(M)L(^)，只需證明L(M)L(M)cL(M),L(M)L(M)mL(M)1.證明L(M1)L(M2)cL(M)設(shè)xeL(M)L(M),從而有工eL(M)并且xeL(M),121122使得x=xxm]在處理氣的過程中,經(jīng)過的狀態(tài)全部都是q中的狀態(tài)，所以在定義M時，對VgeQ,aeE,5(q,x)=5(q,a)故8(q,x)=5(q,x)={f}TOC\o"1-5"\h\z01110121M2在處理七的過程中,經(jīng)過的狀態(tài)全部都是％中的狀態(tài)，所以在定義M時，對VqeQ,aeE,8(q,x)=5(q,a)5(q,x)=5(q,x)={f}022012下面證明xeL(M)5(q,x)=5(q,xx)

010112=5(5(q,x),x)=5(5(q,x),x)10112=5(f],x2)=5(f],￡x2)=5(5(f],8),x2)=5(q02,x2)=5(q,x)2022={f2}即得證xeL(M)2)再證明L(M)cL(M)L(M)設(shè)xeL(M)，艮口5(q01,x)={f}由于M是從q：啟動的，由M的定義可知,心要達到狀態(tài)八，必須先至虬.由于除了對應(yīng)狀態(tài)轉(zhuǎn)移函數(shù)式5(f1，8)={q02}的移動外，不存在從1出發(fā)的任何其他移動，而且該移動是2的必經(jīng)移動,所以,比存在x的前綴x和后綴x，使得x=xx,并且xTOC\o"1-5"\h\z12121將心從狀態(tài)q引導(dǎo)到狀態(tài)/,x將心從狀態(tài)q引導(dǎo)到狀態(tài)/0112022即5(q,x)=5(q,xx)010112=5(f1，x2)=5(f1，8x2)=5(q,x)這表明xgL(M)xgL(M)從而x=xxgL(M)L(M)1212故L(M)qL(M)L(M)綜上所述，12L(M)=L(M1)L(M2FAM=(QZ8qF)22,2,2,02,2*******************************************************************************(吳丹02282090)18.證明：對于任意的FAM=(Q.Z8q.FAM=(QZ8qF)22,2,2,02,212證明：不妨將這些FA看成DFA212/01、02(q,p)gQ?([q,p],a)=[8(q,a),8(p,a).取M=(Q]xQ/ZfZ2,8,{q0],q」，對于VagZJIZ2，，一/_\1設(shè)：xgL(M)則女=x1x2xk其中xz4gQ,k])使得8(Iq,p],xi)=[81(q,xi),8(p,xi)]/.xigL(M.)nL(M)nxgL(M.)p|L(M)從而可得L(M)qL(M「nL(mJ設(shè)：xgL(M)nL(M)則女=x1x2......xk其中xiGgI1,k])gZAZ有8](q,xi)且82(p,xi)從而使得81212/01、02(q,p)gQ?([q,p],a)=[8(q,a),8(p,a).xigL(m)nxgL(m)從而可得L(MjnL(M)qL(M)綜合(1)(2)可得L(M)=L(M「nL(mJ。又因為faBdfa具有等價性，，所以原命題得證?！啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊皞€個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個19、總結(jié)本章定義的所有FA,歸納出它們的特點，指出它們之間的差別。（吳玉涵02282091）本章學(xué)習(xí)了DFA，NFA,e-NFA,2DFA和2NFA所有的FA都是一個五元組M=（Q,N，5,q0,F）最大的區(qū)別就是狀態(tài)轉(zhuǎn)移函數(shù)5對于DFA，字母表中的每個字母都有唯一確定的狀態(tài)轉(zhuǎn)移函數(shù)。也就是說V5（q,a）EQXS,qGQ，aEN只有唯一確定的狀態(tài)。對于NFA，對于字母表中的每個輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對于8串，是一個到自身的移動。對于sNFA，是指在不接受任何字符的情況下，自動機的狀態(tài)可以發(fā)身轉(zhuǎn)移。對于2DFA，對于字母表中的每個字符，對于每個狀態(tài)都有唯一的狀態(tài)轉(zhuǎn)移，即V5（q，a）EQXS，qEQ，aES只有唯一確定的狀態(tài)。與DFA不同的是，2DFA的讀頭可以在一次狀態(tài)轉(zhuǎn)移中不移動，或者回退一個，或者向下讀一個。對于2NFA，與2DFA相似，但是并不是對于字母表中的每個輸入字符都有轉(zhuǎn)移函數(shù)，2NFA與2DFA的區(qū)別類似于DFA與NFA的區(qū)別?！啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊?******************************************************************************20構(gòu)造如圖3-20所個的DFA對應(yīng)的右線性文法。（周期律02282067）對圖1：構(gòu)造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}ST0A|1|1CAt0S|1|1CP：Bt010C|1SCT0A|1A對圖2：構(gòu)造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}ST0A|1BAt1S|1|0BP：Bt0C|0|1ACT0A|1A“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************21.構(gòu)造下圖所示DFA對應(yīng)的左線性文法。（吳賢珺02282047）⑴圖形如下所示解：設(shè)q0、q1、q2、q3所對應(yīng)的字符分別為A、B、C、G。由于q2為不可達狀態(tài)，故先去掉該狀態(tài)。得到該圖所對應(yīng)的左線性文法為:G-A1|B1|1B-G0|G1|A0|0A—B0⑵圖形如下所示:解：圖中有多個終結(jié)狀態(tài)，為方便起見，增加一個終結(jié)狀態(tài)（紅色表示），設(shè)該狀態(tài)所對應(yīng)的字符為G。又設(shè)q0、q1、q2、q3所對應(yīng)的字符分別為A、B、C、D。則該圖所對應(yīng)的左線性文法為：G-C0|B0|eD-C0C-B0|A1|1B-C1|D0|D1|A0|0A-B1*******************************************************************************22.根據(jù)下列給定文法，構(gòu)造相應(yīng)的FA。(敖雪峰02282068)(1)文法G1的產(chǎn)生式集合如下：G1:S-alAaA-alAalcAlBbB—alblclaBIBblCb(2)文法G2的產(chǎn)生式集合如下：G2:S—alAa

A—alAalAcIBbB—alblcIBalBblBc解答：文法G1對應(yīng)的FA如下所示e“$$$$$$$$$$$$$$$力力力力力力力力$$$$$$$$$$$$$$$$$力、mi，&“$$$$$$$力力力“******************************************************************************23.FAM的移動函數(shù)定義如下：(馮蕊02282075)%3)叫}(q0，1)=(q1}(q1,0)={q2}(q1?1)={q3}5(q2,0)={q2}5(q3,1)={q3}其中,q2,q3為終態(tài).M是DFA嗎?為什么？不是，因為并不是所有的狀態(tài),在接收一個字母表中的字符時會有一個狀態(tài)與之對應(yīng).畫出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖0,1,3⑶給出你所畫出的DFA的每個狀態(tài)q的set(q):set(q)={xlx￡N*且5(q0,x)=q}set(q0)={3*}set(q1)={3*1}set(q2)={3*100*}set(q3)={3*111*}set(q)={(3*013*1313*100*(113)13*111*(013))0*1*3*}⑷求正則方法G/吏L（G）=L（M）q0—3q0|1q1qL0q2|1q3q2一010q2q3—mq3*******************************************************************************24,總結(jié)規(guī)約與派生的對應(yīng)關(guān)系，以及與FA的識別過程的對應(yīng)關(guān)系。（段季芳02282073）答：對于左線性文法來說，句子a1a2....an-1an按派生來看，字符在句子中出現(xiàn)的順序是相反的，即anan-1...a2a1按規(guī)約來看，被規(guī)約成語法變量的順序和他們在句子中出現(xiàn)的順序是一致的，即".??氣-1*FA識別時，如果存在狀態(tài)轉(zhuǎn)移5（A，a）=B，表示A后緊跟一個a時，要規(guī)約到B；如果B是終結(jié)符號，則A后緊跟一個a時，要規(guī)約到該文法的開始符號；如果A是開始狀態(tài)，則a要規(guī)約到B。對于右線性文法來說，句子a1a2....an-1an按派生來看，字符在句子中出現(xiàn)的順序也就是a1a2..an-1an按規(guī)約來看，被規(guī)約成語法變量的順序和他們在句子中出現(xiàn)的順序是相反的，即anan-1...a2a1FA識別時，如果存在狀態(tài)轉(zhuǎn)移5（A，a）=B，則表示遇到A則派生成aB；但如果B是終結(jié)符號，則將A推導(dǎo)為a。******************************************************************************25證明左線性文法與FA等價。（唐明珠02282084）證明：1）根據(jù)左線性G（E）文法構(gòu)造對應(yīng)的FAM=（Q,Z,6,q0,F）為了形如A—。的產(chǎn)生式，增加一個開始狀態(tài)Z，使得q0=Z所以E=F,對于產(chǎn)生式8TAa，則有8(A,a)=B,對于產(chǎn)生式8BTa,且舊是開始狀態(tài)，則有8(E,a)=B.下面證明G(E)與FA等價,即證明L(G(E))=L(M)不會：)2)根據(jù)FAM=(Q,Z,8,q0,F)，構(gòu)造相應(yīng)的G(E)為了方便起見，在根據(jù)給定的FA構(gòu)造等價的左線性文法的之前，先對FA做如下的處理：刪除FA的陷阱狀態(tài)。在FA中增加一個識別狀態(tài)“復(fù)制”一條原來到達終止?fàn)顟B(tài)的弧，使它從原來的起點出發(fā)，到達新添加的識別狀態(tài)。相應(yīng)的文法的構(gòu)造依照如下兩條進行：如果8(A,a)=B，則有產(chǎn)生式BTa如果8(A,a)=B,且A是開始狀態(tài)q0,則有產(chǎn)生式BTa?！啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊?******************************************************************************(吳丹02282090)證明定理3-6。(2DFA與FA等價)證明：對于2DFAM是一個五元組M=(Q，Z，8，q，F(xiàn))其中，Q，Z，q0，F(xiàn)的意義同與DFA。8:QxZtQx{l，R，S}，對于V(q，a)gQx^，如果8(q，a)={p，L}表示在讀入a從狀態(tài)q轉(zhuǎn)移到狀態(tài)p，并將讀頭向左移動，指向輸入字符的前一個字符。如果8(q，a)={p，R}表示在讀入a從狀態(tài)q轉(zhuǎn)移到狀態(tài)p，并將讀頭向右移動，指向輸入字符的下一個字符。如果8(q，a)={p，S}表示在讀入a從狀態(tài)q轉(zhuǎn)移到狀態(tài)p，讀頭保持在原位置不動。我們構(gòu)造與之等價的FA“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““***********************************