形式語言與自動機理論-蔣宗禮-第三章參考答案.doc

《形式語言與自動機理論-蔣宗禮-第三章參考答案.doc》由會員分享，可在線閱讀，更多相關(guān)《形式語言與自動機理論-蔣宗禮-第三章參考答案.doc（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第三章作業(yè)答案 1．已知DFA M1與M2如圖3－18所示。 (敖雪峰 02282068) (1) 請分別給出它們在處理字符串1011001的過程中經(jīng)過的狀態(tài)序列。 (2) 請給出它們的形式描述。 圖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 ( 陶文婧 02282085 ) （1）{0，1}* （2）{0，1}+ （3）{x|x{0，1}+且x中不含00的串} （設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進入陷阱狀態(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è)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進入陷阱狀態(tài)） （7）{x|x{0，1}+且當把x看成二進制時，x模5和3同余，要求當x為0時，|x|=1,且x0時，x的首字符為1 } 1. 以0開頭的串不被接受，故設(shè)置陷阱狀態(tài)，當DFA在啟動狀態(tài)讀入的符號為0，則進入陷阱狀態(tài) 2. 設(shè)置7個狀態(tài)：開始狀態(tài)qs,q0:除以5余0的等價類，q1：除以5余1的等價類,q2:除以5余2的等價類，q3:除以5余3的等價類，q4:除以5余4的等價類，接受狀態(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的第十個字符為1} （設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個字符為0，進入陷阱狀態(tài)） （9）{x|x{0，1}+且x以0開頭以1結(jié)尾} （設(shè)置陷阱狀態(tài)，當?shù)谝粋€字符為1時，進入陷阱狀態(tài)） （10）{x|x{0，1}+且x中至少含有兩個1} （11）{x|x{0，1}+且如果x以1結(jié)尾，則它的長度為偶數(shù)；如果x以0結(jié)尾，則它的長度為奇數(shù)} 可將{0，1}+的字符串分為4個等價類。 q0： [e]的等價類，對應(yīng)的狀態(tài)為終止狀態(tài) q1:x的長度為奇且以0結(jié)尾的等價類 q2：x的長度為奇且以1結(jié)尾的等價類 q3: x的長度為偶且以0結(jié)尾的等價類 q4: x的長度為偶且以1結(jié)尾的等價類 （12）{x|x是十進制非負數(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看成二進制數(shù)時，x% 5=1} Set(q2)={x | x +,并且把x看成二進制數(shù)時，x% 5=2} Set(q3)={x | x +,并且把x看成二進制數(shù)時，x% 5=3} Set(q4)={x | x +,并且把x看成二進制數(shù)時，x% 5=4} Set(q0)={x | x +,并且把x看成二進制數(shù)時，x% 5=0并且x不為0} (8) M={Q, ,,q0,F} Q={q0,q1,q2,…q10} ={0,1} 當0<=i<=8時候， (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的第十個字符是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開頭以0結(jié)尾 } Set(q2)={x | x +,并且x以0開頭以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中只有一個1 } Set(q2)={x | x +,并且x至少有倆個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é)尾，長度為奇數(shù) } Set(q2)={x | x +,以1結(jié)尾，長度為偶數(shù) } Set(q3)={x | x +,以0結(jié)尾，長度為偶數(shù) } Set(q4)={x | x +,以1結(jié)尾，長度為奇數(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)={十進制正整數(shù)} Set(q3)={十進制非負整數(shù)后面接個小數(shù)點 . } Set(q4)={十進制正小數(shù)} （13） Set(q0)= {} Set(q0)= （14） Set(q0)= {} ******************************************************************************* 4 在例3-6中，狀態(tài)采用的形式，它比較清楚地表達出該狀態(tài)所對應(yīng)的記憶內(nèi)容，給我們解決此問題帶來了很大的方便，我們是否可以直接用代替呢？如果能，為什么？如果不能，又是為什么？從此問題的討論，你能總結(jié)出什么來？ （唐明珠 02282084） 答：我認為能夠直接用代替，因為在例3-6中，只是一種新的表示方法，用來表示狀態(tài)存儲的字符，這樣就省去了在中逐一給出每一個具體的輸入字符和狀態(tài)的定義。它的作用在于使FA中狀態(tài)定義更加簡潔。 得到結(jié)論：在今后描述FA時，應(yīng)該根據(jù)具體的情況，使用適當?shù)姆椒ā? ******************************************************************************* 5．試區(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) 6．證明：題目有不嚴密之處，圖中給出DFA與題目中的語言L（M）={x|x x{0，1}+ 且x中0的個數(shù)和1的個數(shù)相等}不完全對應(yīng)，首先圖中的DFA可接受空字符串，而L（M）不接受，其次，對于有些句子，例如1100，L（M）可以接受，但DFA不接受 （1）根據(jù)圖中的DFA可看出，右下角的狀態(tài)為陷阱狀態(tài)，所以去除陷阱狀態(tài) （2）由DFA可構(gòu)造出與其對應(yīng)的右線性文法： （劉鈺 02282083） 由此可以看出該文法接受的語言為L={(10|01)*},顯然01或10分別是作為整體出現(xiàn)的，所以L(M)中0和1的個數(shù)相等。 ****************************************************************************** 7．設(shè)DFA M=，證明：對于 注：采用歸納證明的思路 證明： (周期律02282067) 首先對y歸納，對任意x來說，|y| = 0時，即y= 根據(jù)DFA定義,故原式成立。 當|y| = n時，假設(shè)原式成立，故當|y|= n+1時， 不妨設(shè)y = wa, |w| = n, |a| = 1 根據(jù)DFA定義，故 原式成立， 同理可證，對任意的y來說，結(jié)論也是成立的。 綜上所述，原式得證 ******************************************************************************* 8．證明:對于任意的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） 對任意xΣ* x L(M2)=Σ*—L（M1）δ(q,x)Q—F1δ（q,x）Q并且δ（q,x）F1xΣ*并且xL(M1)xΣ*—L（M1） ******************************************************************************* 9. 對于任意的DFA M1=(Q1,∑,δ1,q01,F1),請構(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) 對于" q,p∈Q1,a∈∑,如果δ1(q,a)=p,q∈δ(p,a) 3) δ(q0,ε)= F1 (2) 證明：L(M)=L(M1)T 對" 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) 同理可證對于" 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}) 等價的NFA M3=( Q,∑,δ2, q0,{ q01}) 其中對于"（q,a）∈Q*∑ δ2(q,a)=δ^ (q,a) 然后按照以前學(xué)過的方法構(gòu)造與NFA M3=( Q,∑,δ2, q0,{ q01})等價的DFA M1=(Q1,∑,δ1,[q0],F1) 其中：Q1=2Q F1={ q01} δ1([q1,q2 ,… ,qn],a)=[p1,p2 ,…,pn] 當且僅當δ2({q1,q2 ,… ,qn },a)={ p1,p2 ,…,pn } ******************************************************************************* 注：此題（10題）張友坤、吳玉涵所做完全一樣！！ 10、構(gòu)造識別下列語言的NFA （吳玉涵02282091） 這是最基本的單元，其他的可以通過這個逐級構(gòu)造出來，以滿足題目要求。 *******************************************************************************11.根據(jù)給定的NFA，構(gòu)造與之等價的DFA. （吳丹 02282090） （1） NFA M1 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(tài) q0 {q0,q1} {q0,q2} {q0,q2} q1 {q3,q0} {q2} q2 {q3,q1} {q2,q1} 終止狀態(tài) q3 {q3,q2} {q3 } { q0} 解答： 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(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] 終止狀態(tài) [q0,q1,q3] [q0,q1,q2,q3] [q0, q2,q3] [q0,q1,q2] 終止狀態(tài) [q0,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0, q2] 終止狀態(tài) [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1, q2] 圖3-9所示NFA等價的DFA （2）NFA M2 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-10 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(tài) q0 {q1,q3} {q1} {q0 } q1 {q2} {q1,q2} {q1} q2 {q3,q2} {q0} {q2 } 終止狀態(tài) q3 {q0 } { q3} 解答： 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(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] 終止狀態(tài) [q2,q3] [q2,q3] [q0] [q2,q3] 終止狀態(tài) [q1,q2,q3] [q2,q3] [q0,q1,q2] [q1, q2,q3] 圖3-10所示NFA等價的DFA **************************************************************************** 12．證明對于任意的NFA，存在與之等價的NFA,該NFA最多只有一個終止狀態(tài) （劉鈺 02282083） 證明：對于任意的NFA M=(Q，∑，δ，q0，F(xiàn)) ，我們?nèi)绻軜?gòu)造出一個只有一個終止狀態(tài)的NFA，并且與之等價，即可證明上面的定理 而對于任意的NFA存在下面兩種情況： (1)終止狀態(tài)只有一個 (2)終止狀態(tài)有多個 要構(gòu)造這個等價的NFA,可以采用如下方法： 對(1)無需變化，該NFA即為滿足條件的NFA 對(2)可以在該NFA的狀態(tài)圖上添加一個新的終止狀態(tài)，并將原來的多個終止狀態(tài)所連接的弧復(fù)制到該狀態(tài)上，此時這個終止狀態(tài)為新狀態(tài)圖中唯一的終止狀態(tài)，且這個新的NFA與原NFA等價，滿足條件 我們總能構(gòu)造出這樣的NFA 因此對于任意的NFA，存在與之等價的NFA,該NFA最多只有一個終止狀態(tài) ******************************************************************************* 13．試給出一個構(gòu)造方法，對于任意的NFA ，構(gòu)造NFA ，使得 注：轉(zhuǎn)化成相應(yīng)的DFA進行處理，然后可參考第8題的思路 證明： (周期律02282067) 首先構(gòu)造一個與NFA 等價的DFA ，根據(jù)定理3.1（P106）， 構(gòu)造其中 在此基礎(chǔ)上， 即取所有確定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。 為了證明，我們在的基礎(chǔ)上，其中，即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然 則又因為故，故 同理容易證明 故，又因為，故 可知，構(gòu)造的是符合要求的。 ******************************************************************************* 14．構(gòu)造識別下列語言的ε-NFA。 (吳賢珺 02282047) ⑴ { x│x∈{0,1}+ 且x中含形如10110的子串 }∪{ x│x∈{0,1}+ 和x的倒數(shù)第10個字符是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個字符是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開頭以1結(jié)尾 }。 解：關(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: 表示q1狀態(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)。 故得到的ε-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}。由此對以后每輸入一個字符后得到的新狀態(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}，因為q3為終止狀態(tài)，所以q2={ q0, q1，q2，q3}為終止狀態(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}因為各狀態(tài)均含有終止狀態(tài)，所以q0, q1，q2，q3,q4均為終止狀態(tài) 注：本題沒有必要按照NFA到DFA轉(zhuǎn)化的方法來做，而且從e-NFA到NFA轉(zhuǎn)化時狀態(tài)沒有必要改變，可以完全采用e-NFA中的狀態(tài) 如（1） 狀態(tài) 0 1 q0(開始狀態(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（終止狀態(tài)） { q0, q1，q2，q3} { q0, q1，q2，q3} (2) 狀態(tài) 0 1 q0(開始狀態(tài)) { q1 q2 q3， } { q0, q1，q2，q3} q1 { q2} { q1，q2} q2 {，q2，q3} { q0, q2，q3} q3（終止狀態(tài)） 空 { q0 } ******************************************************************************* 16. 證明對于"的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} 對于" q∈Q1,a∈∑1δ(q, a)=δ1(q,a) 對于" 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)，當x ∈L(M1)時 δ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) 同理可證當x ∈L(M2)時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) 因為Q1 與Q2的交集為空 而且δ（q0,x）∈F F= F1∪F2 則 δ(q01 , x)= δ1(q01 , x)∈F1 因此x∈L(M1) 如果是δ(q02 , x) 因為Q1 與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 證明：對于任意的FA . 證明：令 ,其中δ的定義為： 1) 對"q∈Q1-{f1}，a∈∑∪{ε} δ(q，a)=δ1(q，a)； 2) 對"q∈Q2-{f2}，a∈∑∪{ε} δ(q，a)=δ2(q，a)； 3) δ(f1，ε)={q02} 要證 ， 只需證明 ， 1. 證明 2) 再證明 ******************************************************************************* （吳丹 02282090） ***************************************************************************** 19、總結(jié)本章定義的所有FA，歸納出它們的特點，指出它們之間的差別。（吳玉涵02282091） 本章學(xué)習(xí)了DFA，NFA，ε-NFA，2DFA和2NFA 所有的FA都是一個五元組M=（Q，Σ，δ，q0，F(xiàn)） 最大的區(qū)別就是狀態(tài)轉(zhuǎn)移函數(shù)δ 對于DFA，字母表中的每個字母都有唯一確定的狀態(tài)轉(zhuǎn)移函數(shù)。也就是說δ（q，a）∈QΣ，q∈Q，a∈Σ只有唯一確定的狀態(tài)。 對于NFA，對于字母表中的每個輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對于ε串，是一個到自身的移動。 對于ε-NFA，是指在不接受任何字符的情況下，自動機的狀態(tài)可以發(fā)身轉(zhuǎn)移。 對于2DFA，對于字母表中的每個字符，對于每個狀態(tài)都有唯一的狀態(tài)轉(zhuǎn)移，即δ（q，a）∈QΣ，q∈Q，a∈Σ只有唯一確定的狀態(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} P： 對圖2：構(gòu)造文法G=（V，T，P，S），其中 V={S，A，B，C}，T={1，0} P： ******************************************************************************* 21．構(gòu)造下圖所示DFA對應(yīng)的左線性文法。 (吳賢珺 02282047) ⑴ 圖形如下所示 0 0 1 0, 1 1 0 1 q0 q1 q2 q3 S 解：設(shè)q0、q1、q2、q3所對應(yīng)的字符分別為A、B、C、G。 由于q2為不可達狀態(tài)，故先去掉該狀態(tài)。得到該圖所對應(yīng)的左線性文法為： 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 解：圖中有多個終結(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│ε 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對應(yīng)的FA如下所示 文法G2對應(yīng)的FA如下所示 ****************************************************************************** 23.FA M的移動函數(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嗎?為什么? 不是,因為并不是所有的狀態(tài),在接收一個字母表中的字符時會有一個狀態(tài)與之對應(yīng). (2) 畫出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖 (3) 給出你所畫出的DFA的每個狀態(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ī)約與派生的對應(yīng)關(guān)系，以及與FA的識別過程的對應(yīng)關(guān)系。（段季芳02282073） 答：對于左線性文法來說，句子a1a2….an-1an 按派生來看，字符在句子中出現(xiàn)的順序是相反的，即anan-1…a2a1 按規(guī)約來看，被規(guī)約成語法變量的順序和他們在句子中出現(xiàn)的順序 是一致的，即a1a2….an-1an FA識別時，如果存在狀態(tài)轉(zhuǎn)移δ（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…a2a1 FA識別時，如果存在狀態(tài)轉(zhuǎn)移δ（A，a）=B，則表示遇到A則派生成aB；但如果B是終結(jié)符號，則將A推導(dǎo)為a。 ****************************************************************************** 25 證明左線性文法與FA等價。 （唐明珠 02282084） 證明：1）根據(jù)左線性G(E)文法構(gòu)造對應(yīng)的FA 為了形如 所以E=F, 對于產(chǎn)生式 下面證明G(E)與FA等價,即證明L(G(E))=L(M) 不會：） 2）根據(jù)FA ，構(gòu)造相應(yīng)的G(E) 為了方便起見，在根據(jù)給定的FA構(gòu)造等價的左線性文法的之前，先對FA做如下的處理： 1. 刪除FA的陷阱狀態(tài)。 2. 在FA中增加一個識別狀態(tài) 3. “復(fù)制”一條原來到達終止狀態(tài)的弧，使它從原來的起點出發(fā)，到達新添加的識別狀態(tài)。 相應(yīng)的文法的構(gòu)造依照如下兩條進行： 1. 如果 2. 如果。 ******************************************************************************* （吳丹 02282090） ******************************************************************************* 27．證明定理3-7 (周期律02282067) 證明： 因為FA是一種特殊的2NFA，他是當時，都有 ，此時的D只為往右移動，即一個每一個狀態(tài)讀入一個字符后讀頭都往右移動指向下一字符的2NFA，故對任意的FA，定會找到一個與之等價的2NFA與之對應(yīng)。 因此我們只需要證明對任何的2NFA ，都存在FA 與之等價。 對于任何的2NFA ，構(gòu)造FA ， 按三個方式構(gòu)造： 1．如果則； 2．如果則如果，則；如果，則重復(fù)第二步；如果，則對于 集合A = ，。 3．如果則設(shè)集合A = ， ******************************************************************************* 28．證明定理3-8：Moore機與Mealy機等價 （郭會 02282015） 證明： 不妨設(shè)Moore機，Mealy機，則根據(jù)Moore機和Mealy機等價的定義知，必須證明：,其中T1(x)和T2(x)分別表示M1和M2關(guān)于x的輸出。 （1） 構(gòu)造M2， （2） 證明， 不妨設(shè) 則M1的輸出為: 由題意可知 均為Moore機中的狀態(tài)，由（1）中的構(gòu)造假設(shè)知，M2的輸出為： （1） 構(gòu)造M1， （2） 證明， 不妨設(shè) 則M1的輸出為: 由題意可知 均為Mealy機中的狀態(tài)，由（1）中的構(gòu)造假設(shè)知，M1的輸出為： 綜上所述，Moore機與Mealy機等價