形式語(yǔ)言與自動(dòng)機(jī)理論-蔣宗禮-第三章參考答案

《形式語(yǔ)言與自動(dòng)機(jī)理論-蔣宗禮-第三章參考答案》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《形式語(yǔ)言與自動(dòng)機(jī)理論-蔣宗禮-第三章參考答案（30頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第三章作業(yè)答案 1．已知DFA M1與M2如圖3－18所示。 (敖雪峰 02282068) (1) 請(qǐng)分別給出它們?cè)谔幚碜址?011001的過(guò)程中經(jīng)過(guò)的狀態(tài)序列。 (2) 請(qǐng)給出它們的形式描述。 圖3－18 兩個(gè)不同的DFA 解答：(1)M1在處理1011001的過(guò)程中經(jīng)過(guò)的狀態(tài)序列為q0q3q1q3q2q3q1q3; M2在處理1011001的過(guò)程中經(jīng)過(guò)的狀態(tài)序列為q0q2q3q1q3q2q3q1; (2)考慮到用形式語(yǔ)言表示,用自然語(yǔ)言似乎不是那么容易,所以用圖上作業(yè)法把它們用正則表達(dá)式來(lái)描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．構(gòu)造下列語(yǔ)言的DFA ( 陶文婧 02282085 ) （1）{0，1}* （2）{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)） （5）{x|x{0，1}+且x中含形如10110的子串} （6）{x|x{0，1}+且x中不含形如10110的子串} （設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進(jìn)入陷阱狀態(tài)） （7）{x|x{0，1}+且當(dāng)把x看成二進(jìn)制時(shí)，x模5和3同余，要求當(dāng)x為0時(shí)，|x|=1,且x0時(shí)，x的首字符為1 } 1. 以0開(kāi)頭的串不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)DFA在啟動(dòng)狀態(tài)讀入的符號(hào)為0，則進(jìn)入陷阱狀態(tài) 2. 設(shè)置7個(gè)狀態(tài)：開(kāi)始狀態(tài)qs,q0:除以5余0的等價(jià)類(lèi)，q1：除以5余1的等價(jià)類(lèi),q2:除以5余2的等價(jià)類(lèi)，q3:除以5余3的等價(jià)類(lèi)，q4:除以5余4的等價(jià)類(lèi)，接受狀態(tài)qt 3. 狀態(tài)轉(zhuǎn)移表為 狀態(tài) 0 1 q0 q1 q2 q1 q3 q2 q2 q0 q4 q3 q1 q2 q4 q3 q4 （8）{x|x{0，1}+且x的第十個(gè)字符為1} （設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個(gè)字符為0，進(jìn)入陷阱狀態(tài)） （9）{x|x{0，1}+且x以0開(kāi)頭以1結(jié)尾} （設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài)） （10）{x|x{0，1}+且x中至少含有兩個(gè)1} （11）{x|x{0，1}+且如果x以1結(jié)尾，則它的長(zhǎng)度為偶數(shù)；如果x以0結(jié)尾，則它的長(zhǎng)度為奇數(shù)} 可將{0，1}+的字符串分為4個(gè)等價(jià)類(lèi)。 q0： [e]的等價(jià)類(lèi)，對(duì)應(yīng)的狀態(tài)為終止?fàn)顟B(tài) q1:x的長(zhǎng)度為奇且以0結(jié)尾的等價(jià)類(lèi) q2：x的長(zhǎng)度為奇且以1結(jié)尾的等價(jià)類(lèi) q3: x的長(zhǎng)度為偶且以0結(jié)尾的等價(jià)類(lèi) q4: x的長(zhǎng)度為偶且以1結(jié)尾的等價(jià)類(lèi) （12）{x|x是十進(jìn)制非負(fù)數(shù)} （13）F （14）e ******************************************************************************* 3 (1) （張友坤02282061） ={0,1} Set(q0)={x | x * } (2) ={0,1} Set(q0)= Set(q1)={x | x + } （3） ={0,1} Set(q0)= Set(q1)={x | x +并且x中不含形如00的子串 } Set(q2)={x | x +并且x中不含形如00的子串 } (4) ={0,1} Set(q0)={x | x *并且x中不含形如00的子串 } Set(q1)={x | x *并且x中不含形如00的子串 } (5) ={0,1} Set(q0)= {x | x *,并且x{0}*或者x中含形如100的子串 } Set(q1)={x | x *,并且x中含形如1的子串} Set(q2)={x | x *,并且x中含形如10的子串 } Set(q3)={x | x *,并且x中含形如101的子串 } Set(q4)={x | x *,并且x中含形如1011的子串 } Set(q5)={x | x *,并且x中含形如10110的子串 } (6) ={0,1} Set(q0)= {} Set(q1)={x | x{0+}} Set(q2)={x | x *,并且x中不含形如10110的子串而且x中含有1} Set(q3)={x | x *,并且x中不含形如10110的子串而且x中含有1} (7) ={0,1} Set(qs)= {} Set(qe)= {0} Set(q1)={x | x +,并且把x看成二進(jìn)制數(shù)時(shí)，x% 5=1} Set(q2)={x | x +,并且把x看成二進(jìn)制數(shù)時(shí)，x% 5=2} Set(q3)={x | x +,并且把x看成二進(jìn)制數(shù)時(shí)，x% 5=3} Set(q4)={x | x +,并且把x看成二進(jìn)制數(shù)時(shí)，x% 5=4} Set(q0)={x | x +,并且把x看成二進(jìn)制數(shù)時(shí)，x% 5=0并且x不為0} (8) M={Q, ,,q0,F} Q={q0,q1,q2,…q10} ={0,1} 當(dāng)0<=i<=8時(shí)候， (q i,0)= ( q i,1)=q（i+1） ( q 9,1)=q10 (q 10,0)= ( q 10,1)=q10 F={ q 10} Set(q0)= {} Set(q1)= {0,1} Set(q2)={x | x +,并且|x|=2} Set(q3)={x | x +,并且|x|=3} Set(q4)={x | x +,并且|x|=4} Set(q5)={x | x +,并且|x|=5} Set(q6)={x | x +,并且|x|=6} Set(q7)={x | x +,并且|x|=7} Set(q8)={x | x +,并且|x|=8} Set(q9)={x | x +,并且|x|=9} Set(q10)={x | x +,并且x的第十個(gè)字符是1} (9) M={Q, ,,q0,F} Q={q0,q1,q2 } ={0,1} (q 0,0)=q1 (q 1,0)= q1 (q 1,1)= q2 (q 2,1)= q2 (q 2,0)= q1 F={ q 2} Set(q0)= {} Set(q1)={x | x +,并且x以0開(kāi)頭以0結(jié)尾 } Set(q2)={x | x +,并且x以0開(kāi)頭以1結(jié)尾 } (10) M={Q, ,,q0,F} Q={q0,q1,q2 } ={0,1} (q 0,0)=q0 (q 0,1)=q1 (q 1,0)= q1 (q 1,1)= q2 (q 2,1)= q2 (q 2,0)= q2 F={ q 2} Set(q0)= {0}* Set(q1)={x | x +,并且x中只有一個(gè)1 } Set(q2)={x | x +,并且x至少有倆個(gè)1} (11) M={Q, ,,q0,F} Q={q0,q1,q2 , q3,q4 } ={0,1} (q 0,0)=q1 (q 0,1)=q4 (q 1,0)= q3 (q 1,1)= q2 (q 2,1)= q4 (q 2,0)= q1 (q 3,0)= q1 (q 3,1)= q4 (q 4,1)= q2 (q 4,0)= q3 F={ q 0 ,q 1 ,q 2} Set(q0)= {} Set(q1)={x | x +,以0結(jié)尾，長(zhǎng)度為奇數(shù) } Set(q2)={x | x +,以1結(jié)尾，長(zhǎng)度為偶數(shù) } Set(q3)={x | x +,以0結(jié)尾，長(zhǎng)度為偶數(shù) } Set(q4)={x | x +,以1結(jié)尾，長(zhǎng)度為奇數(shù) } (12) M={Q, ,,q0,F} Q={q0,q1,q2,q3,q4} ={.,0,1,2,…,9} F={q1,q2,q4} (q 0,0)=q1 (q 0,1|2|3|4|5|6|7|8|9)=q2 (q 1, . )=q2 (q 2,0|1|2|3|4|5|6|7|8|9)=q2 (q 2, . )=q3 (q 3,0|1|2|3|4|5|6|7|8|9)=q4 (q 4,0|1|2|3|4|5|6|7|8|9)=q4 Set(q0)= {} Set(q1)={0 } Set(q2)={十進(jìn)制正整數(shù)} Set(q3)={十進(jìn)制非負(fù)整數(shù)后面接個(gè)小數(shù)點(diǎn) . } Set(q4)={十進(jìn)制正小數(shù)} （13） Set(q0)= {} Set(q0)= （14） Set(q0)= {} ******************************************************************************* 4 在例3-6中，狀態(tài)采用的形式，它比較清楚地表達(dá)出該狀態(tài)所對(duì)應(yīng)的記憶內(nèi)容，給我們解決此問(wèn)題帶來(lái)了很大的方便，我們是否可以直接用代替呢？如果能，為什么？如果不能，又是為什么？從此問(wèn)題的討論，你能總結(jié)出什么來(lái)？ （唐明珠 02282084） 答：我認(rèn)為能夠直接用代替，因?yàn)樵诶?-6中，只是一種新的表示方法，用來(lái)表示狀態(tài)存儲(chǔ)的字符，這樣就省去了在中逐一給出每一個(gè)具體的輸入字符和狀態(tài)的定義。它的作用在于使FA中狀態(tài)定義更加簡(jiǎn)潔。 得到結(jié)論：在今后描述FA時(shí)，應(yīng)該根據(jù)具體的情況，使用適當(dāng)?shù)姆椒ā? ******************************************************************************* 5．試區(qū)別FA中的陷阱狀態(tài)和不可達(dá)狀態(tài)。 （吳賢珺 02282047） 解：⑴ 陷阱狀態(tài)（課本97頁(yè)）：指在其它狀態(tài)下發(fā)現(xiàn)輸入串不可能是該FA所識(shí)別的句子時(shí)所進(jìn)入的狀態(tài)。FA一旦進(jìn)入該狀態(tài)，就無(wú)法離開(kāi)，并在此狀態(tài)下，讀完輸入串中剩余的字符。 ⑵ 不可達(dá)狀態(tài)（課本108頁(yè)）：指從FA的開(kāi)始狀態(tài)出發(fā)，不可能到達(dá)的狀態(tài)。就FA的狀態(tài)轉(zhuǎn)移圖來(lái)說(shuō)，就是不存在從開(kāi)始狀態(tài)對(duì)應(yīng)的頂點(diǎn)出發(fā)，到達(dá)該狀態(tài)對(duì)應(yīng)頂點(diǎn)的路徑。 ⑶ 從兩者的定義可見(jiàn)：相對(duì)于不可達(dá)狀態(tài)來(lái)說(shuō)，陷阱狀態(tài)是可達(dá)的。但是，它們都是狀態(tài)轉(zhuǎn)移圖中的非正常狀態(tài)。如果從狀態(tài)轉(zhuǎn)移圖中的狀態(tài)引一條弧到不可達(dá)狀態(tài)，同時(shí)不可達(dá)狀態(tài)所有的移動(dòng)都是到自身。這樣，不可達(dá)狀態(tài)就變成了陷阱狀態(tài)。 ****************************************************************************** 注：此題目有問(wèn)題，可以將題設(shè)改為：x中0和1個(gè)數(shù)相等且交替出現(xiàn) 6．證明：題目有不嚴(yán)密之處，圖中給出DFA與題目中的語(yǔ)言L(fǎng)（M）={x|x x{0，1}+ 且x中0的個(gè)數(shù)和1的個(gè)數(shù)相等}不完全對(duì)應(yīng)，首先圖中的DFA可接受空字符串，而L（M）不接受，其次，對(duì)于有些句子，例如1100，L（M）可以接受，但DFA不接受 （1）根據(jù)圖中的DFA可看出，右下角的狀態(tài)為陷阱狀態(tài)，所以去除陷阱狀態(tài) （2）由DFA可構(gòu)造出與其對(duì)應(yīng)的右線(xiàn)性文法： （劉鈺 02282083） 由此可以看出該文法接受的語(yǔ)言為L(zhǎng)={(10|01)*},顯然01或10分別是作為整體出現(xiàn)的，所以L(fǎng)(M)中0和1的個(gè)數(shù)相等。 ****************************************************************************** 7．設(shè)DFA M=，證明：對(duì)于 注：采用歸納證明的思路 證明： (周期律02282067) 首先對(duì)y歸納，對(duì)任意x來(lái)說(shuō)，|y| = 0時(shí)，即y= 根據(jù)DFA定義,故原式成立。 當(dāng)|y| = n時(shí)，假設(shè)原式成立，故當(dāng)|y|= n+1時(shí)， 不妨設(shè)y = wa, |w| = n, |a| = 1 根據(jù)DFA定義，故 原式成立， 同理可證，對(duì)任意的y來(lái)說(shuō)，結(jié)論也是成立的。 綜上所述，原式得證 ******************************************************************************* 8．證明:對(duì)于任意的DFA M1=(Q,Σ,δ,q0,F1) 存在DFA M2=(Q,Σ,δ,q0,F2), （馮蕊 02282075） 使得L(M2)=Σ*—L（M1）。 證明：（1）構(gòu)造M2。 設(shè)DFA M1=(Q,Σ,δ,q0,F1) 取DFA M2=(Q,Σ,δ,q0,Q—F1) （2）證明L(M2)=Σ*—L（M1） 對(duì)任意xΣ* x L(M2)=Σ*—L（M1）δ(q,x)Q—F1δ（q,x）Q并且δ（q,x）F1xΣ*并且xL(M1)xΣ*—L（M1） ******************************************************************************* 9. 對(duì)于任意的DFA M1=(Q1,∑,δ1,q01,F1),請(qǐng)構(gòu)造DFA M1=(Q2,∑,δ2,q02,F2)，使得L(M1)=L(M2)T 。其中L(M)T={x|xT∈L(M)} （褚穎娜 02282072） (1) 構(gòu)造ε-NFA M 使得 L(M)=L(M1) 取ε-NFA M=( Q,∑,δ, q0,{ q01}) 其中: 1) Q= Q1∪{ q0}, q0 Q1 2) 對(duì)于" q,p∈Q1,a∈∑,如果δ1(q,a)=p,q∈δ(p,a) 3) δ(q0,ε)= F1 (2) 證明：L(M)=L(M1)T 對(duì)" x=a1 a2… am∈L(M) q0 a1 a2… am├qf a1 a2… am├a1 q1 a2… am├a1 a2 q2… am├…├a1 a2…qm-1am ├a1 a2…am q01 其中qf∈δ(q0,ε), q1∈δ(qf, a1), q2∈δ(q1, a2),…q01∈δ(qm-1, am) 并且qf∈F1 則δ1(q01, am)= qm-1, δ1(qm-1, am-1)= qm-2,…δ1(q2, a2)= q1δ1(q1, a1)= qf 因此q01 am am-1…a1├am qm-1 am-1…a1├am am-1…q2 a2 a1├am am-1… a2 q1a1 ├am am-1… a2 a1qf 因此am am-1…a1∈L(M1) 即 xT∈L(M1) 同理可證對(duì)于" x=a1 a2… am∈L(M1) xT=am am-1…a1∈L(M1) L(M)=L(M1)T得證 （3）將ε-NFA M 確定化 首先構(gòu)造與ε-NFA M=( Q,∑,δ, q0,{ q01}) 等價(jià)的NFA M3=( Q,∑,δ2, q0,{ q01}) 其中對(duì)于"（q,a）∈Q*∑ δ2(q,a)=δ^ (q,a) 然后按照以前學(xué)過(guò)的方法構(gòu)造與NFA M3=( Q,∑,δ2, q0,{ q01})等價(jià)的DFA M1=(Q1,∑,δ1,[q0],F1) 其中：Q1=2Q F1={ q01} δ1([q1,q2 ,… ,qn],a)=[p1,p2 ,…,pn] 當(dāng)且僅當(dāng)δ2({q1,q2 ,… ,qn },a)={ p1,p2 ,…,pn } ******************************************************************************* 注：此題（10題）張友坤、吳玉涵所做完全一樣！！ 10、構(gòu)造識(shí)別下列語(yǔ)言的NFA （吳玉涵02282091） 這是最基本的單元，其他的可以通過(guò)這個(gè)逐級(jí)構(gòu)造出來(lái)，以滿(mǎn)足題目要求。 *******************************************************************************11.根據(jù)給定的NFA，構(gòu)造與之等價(jià)的DFA. （吳丹 02282090） （1） NFA M1 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9 狀態(tài)說(shuō)明 狀態(tài) 輸入字符 0 1 2 開(kāi)始狀態(tài) q0 {q0,q1} {q0,q2} {q0,q2} q1 {q3,q0} {q2} q2 {q3,q1} {q2,q1} 終止?fàn)顟B(tài) q3 {q3,q2} {q3 } { q0} 解答： 狀態(tài)說(shuō)明 狀態(tài) 輸入字符 0 1 2 開(kāi)始狀態(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] 圖3-9所示NFA等價(jià)的DFA （2）NFA M2 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-10 狀態(tài)說(shuō)明 狀態(tài) 輸入字符 0 1 2 開(kāi)始狀態(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)說(shuō)明 狀態(tài) 輸入字符 0 1 2 開(kāi)始狀態(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] 圖3-10所示NFA等價(jià)的DFA **************************************************************************** 12．證明對(duì)于任意的NFA，存在與之等價(jià)的NFA,該NFA最多只有一個(gè)終止?fàn)顟B(tài) （劉鈺 02282083） 證明：對(duì)于任意的NFA M=(Q，∑，δ，q0，F(xiàn)) ，我們?nèi)绻軜?gòu)造出一個(gè)只有一個(gè)終止?fàn)顟B(tài)的NFA，并且與之等價(jià)，即可證明上面的定理 而對(duì)于任意的NFA存在下面兩種情況： (1)終止?fàn)顟B(tài)只有一個(gè) (2)終止?fàn)顟B(tài)有多個(gè) 要構(gòu)造這個(gè)等價(jià)的NFA,可以采用如下方法： 對(duì)(1)無(wú)需變化，該NFA即為滿(mǎn)足條件的NFA 對(duì)(2)可以在該NFA的狀態(tài)圖上添加一個(gè)新的終止?fàn)顟B(tài)，并將原來(lái)的多個(gè)終止?fàn)顟B(tài)所連接的弧復(fù)制到該狀態(tài)上，此時(shí)這個(gè)終止?fàn)顟B(tài)為新?tīng)顟B(tài)圖中唯一的終止?fàn)顟B(tài)，且這個(gè)新的NFA與原NFA等價(jià)，滿(mǎn)足條件 我們總能構(gòu)造出這樣的NFA 因此對(duì)于任意的NFA，存在與之等價(jià)的NFA,該NFA最多只有一個(gè)終止?fàn)顟B(tài) ******************************************************************************* 13．試給出一個(gè)構(gòu)造方法，對(duì)于任意的NFA ，構(gòu)造NFA ，使得 注：轉(zhuǎn)化成相應(yīng)的DFA進(jìn)行處理，然后可參考第8題的思路 證明： (周期律02282067) 首先構(gòu)造一個(gè)與NFA 等價(jià)的DFA ，根據(jù)定理3.1（P106）， 構(gòu)造其中 在此基礎(chǔ)上， 即取所有確定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。 為了證明，我們?cè)诘幕A(chǔ)上，其中，即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然 則又因?yàn)楣?，? 同理容易證明 故，又因?yàn)?，? 可知，構(gòu)造的是符合要求的。 ******************************************************************************* 14．構(gòu)造識(shí)別下列語(yǔ)言的ε-NFA。 (吳賢珺 02282047) ⑴ { x│x∈{0,1}+ 且x中含形如10110的子串 }∪{ x│x∈{0,1}+ 和x的倒數(shù)第10個(gè)字符是1，且以01結(jié)尾 }。 解：得到的ε-NFA如下所示： ε 0, 1 0, 1 1 1 1 00 00 S0 0, 1 1 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 0 1 ε 0, 1 0 0, 1 1 1 1 00 00 S0 0, 1 1 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 0 1 ε ε ε ⑵ { x│x∈{0,1}+ 且x中含形如10110的子串 }{ x│x∈{0,1}+ 和x的倒數(shù)第10個(gè)字符是1，且以01結(jié)尾 } 解：得到的ε-NFA如下所示： 0, 1 0, 1 1 1 1 00 00 0, 1 1 0, 1 0, 1 0,1 1 0, 1 0, 1 0,1 11 0, 1 0 1 S ε ⑶ { x│x∈{0,1}+ 且x中不含形如10110的子串 }∪{ x│x∈{0,1}+且x以0開(kāi)頭以1結(jié)尾 }。 解：關(guān)鍵是構(gòu)造第一個(gè)FA，方法是設(shè)置5個(gè)狀態(tài)： q0：表示開(kāi)始狀態(tài)，以及連續(xù)出現(xiàn)了兩個(gè)以上的0時(shí)所進(jìn)入的狀態(tài)。 q1: 表示q0狀態(tài)下接受到1時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0后輸入1時(shí)）所進(jìn)入的狀態(tài)。 q2: 表示q1狀態(tài)下接受到0時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0后輸入10時(shí)）所進(jìn)入的狀態(tài)。 q3: 表示q2狀態(tài)下接受到1時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0后輸入101時(shí)）所進(jìn)入的狀態(tài)。 q4: 表示q3狀態(tài)下接受到1時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0后輸入1011時(shí)）所進(jìn)入的狀態(tài)。 故得到的ε-NFA如下所示： S ε ε 0 1 1 0 q1 q0 q2 q3 q4 1 0 1 1 0 ε ε ε ε ε F 0 0, 1 1 s0 s1 s2 ε 1 ⑷ { x│x∈{0,1}+ 且x中不含形如00的子串 }{ x│x∈{0,1}+ 且x中不含形如11的子串 }。 解：得到的ε-NFA如下所示： 1 0 1 1 0, 1 ε 0 1 0 0 0, 1 S 另外，本題可以構(gòu)造DFA如下（其中qt為陷阱狀態(tài)）： q0 q1 0 q2 1 S 1 1 1 q4 0 q5 1 0 0 q3 0 0 1 q6 0 1 qt 0, 1 ⑸ { x│x∈{0,1}+ 且x中不含形如00的子串 }∩{ x│x∈{0,1}+ 且x中不含形如11的子串 }。 解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相間的串。所以，得到的ε-NFA如下所示： ε ε 0 1 ε ε ε ε 1 ε 0 ε S 另外，本題可以構(gòu)造DFA如下（其中q+為陷阱狀態(tài)）： S 0 1 0 1 0 1 0 1 1 0 qt 0,1 ******************************************************************************* 15．（1）根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù)，起始狀態(tài)q0的e閉包為 e-CLOSURE（q0）={ q0, q2}。由此對(duì)以后每輸入一個(gè)字符后得到的新?tīng)顟B(tài)再做e閉包，得到下表： （陶文婧 02282085） 狀態(tài) 0 1 { q0, q2} { q0, q1，q2} { q0, q1，q2，q3} { q0, q1，q2} { q0, q1，q2，q3} { q0, q1，q2，q3} { q0, q1，q2，q3} { q0, q1，q2，q3} { q0, q1，q2，q3} q0={ q0, q2}，q1={ q0, q1，q2}，q2={ q0, q1，q2，q3}，因?yàn)閝3為終止?fàn)顟B(tài)，所以q2={ q0, q1，q2，q3}為終止?fàn)顟B(tài) （2）又上述方法得 狀態(tài) 0 1 { q1, q3} { q3，q2} { q0, q1，q2，q3} { q3，q2} { q3，q2} { q0, q1，q3} { q0, q1，q2，q3} { q1，q2，q3} { q0, q1，q2，q3} { q0, q1，q3} { q1，q2，q3} { q0, q1，q2，q3} { q1，q2，q3} { q3，q2} { q0, q1，q2，q3} q0={ q1, q3}，q1={ q3，q2}，q2={ q0, q1，q2，q3}，q3={ q0, q1，q3}，q4={ q1，q2，q3}因?yàn)楦鳡顟B(tài)均含有終止?fàn)顟B(tài)，所以q0, q1，q2，q3,q4均為終止?fàn)顟B(tài) 注：本題沒(méi)有必要按照NFA到DFA轉(zhuǎn)化的方法來(lái)做，而且從e-NFA到NFA轉(zhuǎn)化時(shí)狀態(tài)沒(méi)有必要改變，可以完全采用e-NFA中的狀態(tài) 如（1） 狀態(tài) 0 1 q0(開(kāi)始狀態(tài)) { q0, q1，q2 q3} { q0, q1，q2，q3} q1 { q0, q1，q2，q3} { q1，q2，q3} q2 { q0, q1，q2，q3} {q1，q2，q3} q3（終止?fàn)顟B(tài)） { q0, q1，q2，q3} { q0, q1，q2，q3} (2) 狀態(tài) 0 1 q0(開(kāi)始狀態(tài)) { q1 q2 q3， } { q0, q1，q2，q3} q1 { q2} { q1，q2} q2 {，q2，q3} { q0, q2，q3} q3（終止?fàn)顟B(tài)） 空 { q0 } ******************************************************************************* 16. 證明對(duì)于"的FA M1=(Q1,∑1,δ1,q01,F1)，F(xiàn)A M1=(Q2,∑2,δ2,q02,F2)，存在FA M， 使得 L(M)= L(M1)∪L(M2) （褚穎娜 02282072） 證明：不妨設(shè)Q1 與Q2的交集為空 （1） 構(gòu)造M=（Q1∪Q2∪{ q0},∑,δ, q0,F）其中： 1）∑=∑1∪∑2 F= F1∪F2 2) δ(q0,ε)={ q01 ,q02} 對(duì)于" q∈Q1,a∈∑1δ(q, a)=δ1(q,a) 對(duì)于" q∈Q2,a∈∑2 ,δ(q, a)=δ2(q,a) (3) 證明： 1）首先證L(M1)∪L(M2)∈L(M) 設(shè) x ∈L(M1)∪L(M2)，從而有x ∈L(M1)或者x ∈L(M2)，當(dāng)x ∈L(M1)時(shí) δ1(q01,x)∈F1 由M的定義可得： δ（q0,x）=δ（q0,εx）=δ(δ(q0,ε), x)=δ({q01 ,q02},x)=δ(q01 , x)∪δ(q02, x) =δ1(q01 , x) ∪δ(q01 , x)∈F1∪δ(q01 , x) 即x∈L(M) 同理可證當(dāng)x ∈L(M2)時(shí)x∈L(M) 故L(M1)∪L(M2)∈L(M) 2) 再證明L(M)∈L(M1)∪L(M2) 設(shè)x∈L(M) 則δ（q0,x）∈F 由M的定義： δ（q0,x）=δ（q0,εx）=δ(δ(q0,ε), x)=δ({q01 ,q02},x) =δ(q01 , x)∪δ(q02, x) 如果是δ(q01 , x) 因?yàn)镼1 與Q2的交集為空 而且δ（q0,x）∈F F= F1∪F2 則 δ(q01 , x)= δ1(q01 , x)∈F1 因此x∈L(M1) 如果是δ(q02 , x) 因?yàn)镼1 與Q2的交集為空 而且δ（q0,x）∈F F= F1∪F2 則 δ(q02 , x)= δ2(q02 , x)∈F1 因此x∈L(M2) 因此x∈L(M1)∪L(M2) L(M)∈L(M1)∪L(M2)得證 因此L(M)= L(M1)∪L(M2) ******************************************************************************* （唐明珠 02282084） 17 證明：對(duì)于任意的FA . 證明：令 ,其中δ的定義為： 1) 對(duì)"q∈Q1-{f1}，a∈∑∪{ε} δ(q，a)=δ1(q，a)； 2) 對(duì)"q∈Q2-{f2}，a∈∑∪{ε} δ(q，a)=δ2(q，a)； 3) δ(f1，ε)={q02} 要證 ， 只需證明 ， 1. 證明 2) 再證明 ******************************************************************************* （吳丹 02282090） ***************************************************************************** 19、總結(jié)本章定義的所有FA，歸納出它們的特點(diǎn)，指出它們之間的差別。（吳玉涵02282091） 本章學(xué)習(xí)了DFA，NFA，ε-NFA，2DFA和2NFA 所有的FA都是一個(gè)五元組M=（Q，Σ，δ，q0，F(xiàn)） 最大的區(qū)別就是狀態(tài)轉(zhuǎn)移函數(shù)δ 對(duì)于DFA，字母表中的每個(gè)字母都有唯一確定的狀態(tài)轉(zhuǎn)移函數(shù)。也就是說(shuō)δ（q，a）∈QΣ，q∈Q，a∈Σ只有唯一確定的狀態(tài)。 對(duì)于NFA，對(duì)于字母表中的每個(gè)輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對(duì)于ε串，是一個(gè)到自身的移動(dòng)。 對(duì)于ε-NFA，是指在不接受任何字符的情況下，自動(dòng)機(jī)的狀態(tài)可以發(fā)身轉(zhuǎn)移。 對(duì)于2DFA，對(duì)于字母表中的每個(gè)字符，對(duì)于每個(gè)狀態(tài)都有唯一的狀態(tài)轉(zhuǎn)移，即δ（q，a）∈QΣ，q∈Q，a∈Σ只有唯一確定的狀態(tài)。與DFA不同的是，2DFA的讀頭可以在一次狀態(tài)轉(zhuǎn)移中不移動(dòng)，或者回退一個(gè)，或者向下讀一個(gè)。 對(duì)于2NFA，與2DFA相似，但是并不是對(duì)于字母表中的每個(gè)輸入字符都有轉(zhuǎn)移函數(shù)，2NFA與2DFA的區(qū)別類(lèi)似于DFA與NFA的區(qū)別。 ******************************************************************************* 20構(gòu)造如圖3-20所個(gè)的DFA對(duì)應(yīng)的右線(xiàn)性文法。 (周期律02282067) 對(duì)圖1：構(gòu)造文法G=（V，T，P，S），其中 V={S，A，B，C}，T={1，0} P： 對(duì)圖2：構(gòu)造文法G=（V，T，P，S），其中 V={S，A，B，C}，T={1，0} P： ******************************************************************************* 21．構(gòu)造下圖所示DFA對(duì)應(yīng)的左線(xiàn)性文法。 (吳賢珺 02282047) ⑴ 圖形如下所示 0 0 1 0, 1 1 0 1 q0 q1 q2 q3 S 解：設(shè)q0、q1、q2、q3所對(duì)應(yīng)的字符分別為A、B、C、G。 由于q2為不可達(dá)狀態(tài)，故先去掉該狀態(tài)。得到該圖所對(duì)應(yīng)的左線(xiàn)性文法為： G→A1│B1│1 B→G0│G1│A0│0 A→B0 ⑵ 圖形如下所示： q0 q1 q2 q3 S 0 1 1 0 1 0 0, 1 0 1 解：圖中有多個(gè)終結(jié)狀態(tài)，為方便起見(jiàn)，增加一個(gè)終結(jié)狀態(tài)（紅色表示），設(shè)該狀態(tài)所對(duì)應(yīng)的字符為G。又設(shè)q0、q1、q2、q3所對(duì)應(yīng)的字符分別為A、B、C、D。 則該圖所對(duì)應(yīng)的左線(xiàn)性文法為： G→C0│B0│ε D→C0 C→B0│A1│1 B→C1│D0│D1│A0│0 A→B1 ******************************************************************************* 22.根據(jù)下列給定文法，構(gòu)造相應(yīng)的FA。 （敖雪峰 02282068） (1) 文法G1的產(chǎn)生式集合如下： G1: S→a|Aa A→a|Aa|cA|Bb B→a|b|c|aB|Bb|Cb (2) 文法G2的產(chǎn)生式集合如下： G2: S→a|Aa A→a|Aa|Ac|Bb B→a|b|c|Ba|Bb|Bc 解答: 文法G1對(duì)應(yīng)的FA如下所示 文法G2對(duì)應(yīng)的FA如下所示 ****************************************************************************** 23.FA M的移動(dòng)函數(shù)定義如下: （馮蕊 02282075） δ(q0,3)={q0} δ(q0,1)={q1} δ(q1,0)={q2} δ(q1,1)={q3} δ(q2,0)={q2} δ(q3,1)={q3} 其中,q2,q3為終態(tài). (1) M是DFA嗎?為什么? 不是,因?yàn)椴⒉皇撬械臓顟B(tài),在接收一個(gè)字母表中的字符時(shí)會(huì)有一個(gè)狀態(tài)與之對(duì)應(yīng). (2) 畫(huà)出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖 (3) 給出你所畫(huà)出的DFA的每個(gè)狀態(tài)q的set(q):set(q)={x|xΣ*且δ(q0,x)=q} set(q0)={3*} set(q1)={ 3*1} set(q2)={ 3*100*} set(q3)={ 3*111*} set(q)={( 3*0|3*13|3*100*(1|3)|3*111*(0|3)) 0*1*3*} (4) 求正則方法G,使L(G)=L(M) q0→3 q0|1 q1 q1→0 q2|1 q3 q2→0|0 q2 q3→1|1 q3 ******************************************************************************* 24，總結(jié)規(guī)約與派生的對(duì)應(yīng)關(guān)系，以及與FA的識(shí)別過(guò)程的對(duì)應(yīng)關(guān)系。（段季芳02282073） 答：對(duì)于左線(xiàn)性文法來(lái)說(shuō)，句子a1a2….an-1an 按派生來(lái)看，字符在句子中出現(xiàn)的順序是相反的，即anan-1…a2a1 按規(guī)約來(lái)看，被規(guī)約成語(yǔ)法變量的順序和他們?cè)诰渥又谐霈F(xiàn)的順序 是一致的，即a1a2….an-1an FA識(shí)別時(shí)，如果存在狀態(tài)轉(zhuǎn)移δ（A，a）=B，表示A后緊跟一個(gè)a時(shí)，要規(guī)約到B；如果B是終結(jié)符號(hào)，則A后緊跟一個(gè)a時(shí)，要規(guī)約到該文法的開(kāi)始符號(hào)；如果A是開(kāi)始狀態(tài)，則a要規(guī)約到B。 對(duì)于右線(xiàn)性文法來(lái)說(shuō)，句子a1a2….an-1an 按派生來(lái)看，字符在句子中出現(xiàn)的順序也就是a1a2….an-1an 按規(guī)約來(lái)看，被規(guī)約成語(yǔ)法變量的順序和他們?cè)诰渥又谐霈F(xiàn)的順序 是相反的，即anan-1…a2a1 FA識(shí)別時(shí)，如果存在狀態(tài)轉(zhuǎn)移δ（A，a）=B，則表示遇到A則派生成aB；但如果B是終結(jié)符號(hào)，則將A推導(dǎo)為a。 ****************************************************************************** 25 證明左線(xiàn)性文法與FA等價(jià)。 （唐明珠 02282084） 證明：1）根據(jù)左線(xiàn)性G(E)文法構(gòu)造對(duì)應(yīng)的FA 為了形如 所以E=F, 對(duì)于產(chǎn)生式 下面證明G(E)與FA等價(jià),即證明L(G(E))=L(M) 不會(huì)：） 2）根據(jù)FA ，構(gòu)造相應(yīng)的G(E) 為了方便起見(jiàn)，在根據(jù)給定的FA構(gòu)造等價(jià)的左線(xiàn)性文法的之前，先對(duì)FA做如下的處理： 1. 刪除FA的陷阱狀態(tài)。 2. 在FA中增加一個(gè)識(shí)別狀態(tài) 3. “復(fù)制”一條原來(lái)到達(dá)終止?fàn)顟B(tài)的弧，使它從原來(lái)的起點(diǎn)出發(fā)，到達(dá)新添加的識(shí)別狀態(tài)。 相應(yīng)的文法的構(gòu)造依照如下兩條進(jìn)行： 1. 如果 2. 如果。 ******************************************************************************* （吳丹 02282090） ******************************************************************************* 27．證明定理3-7 (周期律02282067) 證明： 因?yàn)镕A是一種特殊的2NFA，他是當(dāng)時(shí)，都有 ，此時(shí)的D只為往右移動(dòng)，即一個(gè)每一個(gè)狀態(tài)讀入一個(gè)字符后讀頭都往右移動(dòng)指向下一字符的2NFA，故對(duì)任意的FA，定會(huì)找到一個(gè)與之等價(jià)的2NFA與之對(duì)應(yīng)。 因此我們只需要證明對(duì)任何的2NFA ，都存在FA 與之等價(jià)。 對(duì)于任何的2NFA ，構(gòu)造FA ， 按三個(gè)方式構(gòu)造： 1．如果則； 2．如果則如果，則；如果，則重復(fù)第二步；如果，則對(duì)于 集合A = ，。 3．如果則設(shè)集合A = ， ******************************************************************************* 28．證明定理3-8：Moore機(jī)與Mealy機(jī)等價(jià) （郭會(huì) 02282015） 證明： 不妨設(shè)Moore機(jī)，Mealy機(jī)，則根據(jù)Moore機(jī)和Mealy機(jī)等價(jià)的定義知，必須證明：,其中T1(x)和T2(x)分別表示M1和M2關(guān)于x的輸出。 （1） 構(gòu)造M2， （2） 證明， 不妨設(shè) 則M1的輸出為: 由題意可知 均為Moore機(jī)中的狀態(tài)，由（1）中的構(gòu)造假設(shè)知，M2的輸出為： （1） 構(gòu)造M1， （2） 證明， 不妨設(shè) 則M1的輸出為: 由題意可知 均為Mealy機(jī)中的狀態(tài)，由（1）中的構(gòu)造假設(shè)知，M1的輸出為： 綜上所述，Moore機(jī)與Mealy機(jī)等價(jià)