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

形式語言與自動(dòng)機(jī)理論--第三章參考答案第三章作業(yè)答案1．已知DFAM1與M2如圖3－18所示。(xxxx02282068)請分別給出它們在處理字符串1011001的過程中經(jīng)過的狀態(tài)序列。請給出它們的形式描述。圖3－18兩個(gè)不同的DFA解答：(1)M1在處理1011001的過程中經(jīng)過的狀態(tài)序列為q0q3q1q3q2q3q1q3;M2在處理1011001的過程中經(jīng)過的狀態(tài)序列為q0q2q3q1q3q2q3q1;(2)考慮到用形式語言表示,用自然語言似乎不是那么容易,所以用圖上作業(yè)法把它們用正則表達(dá)式來描述: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(xx02282085)（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}以0開頭的串不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)DFA在啟動(dòng)狀態(tài)讀入的符號為0，則進(jìn)入陷阱狀態(tài)設(shè)置7個(gè)狀態(tài)：開始狀態(tài)qs,q0:除以5余0的等價(jià)類，q1：除以5余1的等價(jià)類,q2:除以5余2的等價(jià)類，q3:除以5余3的等價(jià)類，q4:除以5余4的等價(jià)類，接受狀態(tài)qt狀態(tài)轉(zhuǎn)移表為狀態(tài)01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4（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開頭以1結(jié)尾}（設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài)）（10）{x|x{0，1}+且xxx至少含有兩個(gè)1}（11）{x|x{0，1}+且如果x以1結(jié)尾，則它的xx為偶數(shù)；如果x以0結(jié)尾，則它的xx為奇數(shù)}可將{0，1}+的字符串分為4個(gè)等價(jià)類。q0：[]的等價(jià)類，對應(yīng)的狀態(tài)為終止?fàn)顟B(tài)q1:x的xx為奇且以0結(jié)尾的等價(jià)類q2：x的xx為奇且以1結(jié)尾的等價(jià)類q3:x的xx為偶且以0結(jié)尾的等價(jià)類q4:x的xx為偶且以1結(jié)尾的等價(jià)類（12）{x|x是十進(jìn)制非負(fù)數(shù)}（13）（14）*******************************************************************************3(1)（xx02282061）={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*,并且xxx不含形如10110的子串而且xxx含有1}Set(q3)={x|x*,并且xxx不含形如10110的子串而且xxx含有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í)候，(qi,0)=(qi,1)=q（i+1）(q9,1)=q10(q10,0)=(q10,1)=q10F={q10}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}(q0,0)=q1(q1,0)=q1(q1,1)=q2(q2,1)=q2(q2,0)=q1F={q2}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}(q0,0)=q0(q0,1)=q1(q1,0)=q1(q1,1)=q2(q2,1)=q2(q2,0)=q2F={q2}Set(q0)={0}*Set(q1)={x|x+,并且xxx只有一個(gè)1}Set(q2)={x|x+,并且x至少有倆個(gè)1}(11)M={Q,,,q0,F}Q={q0,q1,q2,q3,q4}={0,1}(q0,0)=q1(q0,1)=q4(q1,0)=q3(q1,1)=q2(q2,1)=q4(q2,0)=q1(q3,0)=q1(q3,1)=q4(q4,1)=q2(q4,0)=q3F={q0,q1,q2}Set(q0)={}Set(q1)={x|x+,以0結(jié)尾，xx為奇數(shù)}Set(q2)={x|x+,以1結(jié)尾，xx為偶數(shù)}Set(q3)={x|x+,以0結(jié)尾，xx為偶數(shù)}Set(q4)={x|x+,以1結(jié)尾，xx為奇數(shù)}(12)M={Q,,,q0,F}Q={q0,q1,q2,q3,q4}={.,0,1,2,…,9}F={q1,q2,q4}(q0,0)=q1(q0,1|2|3|4|5|6|7|8|9)=q2(q1,.)=q2(q2,0|1|2|3|4|5|6|7|8|9)=q2(q2,.)=q3(q3,0|1|2|3|4|5|6|7|8|9)=q4(q4,0|1|2|3|4|5|6|7|8|9)=q4Set(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-6xx，狀態(tài)采用的形式，它比較清楚地表達(dá)出該狀態(tài)所對應(yīng)的記憶內(nèi)容，給我們解決此問題帶來了很大的方便，我們是否可以直接用代替呢？如果能，為什么？如果不能，又是為什么？從此問題的討論，你能總結(jié)出什么來？（xxxx02282084）答：我認(rèn)為能夠直接用代替，因?yàn)樵诶?-6xx，只是一種新的表示方法，用來表示狀態(tài)存儲的字符，這樣就省去了在xx逐一給出每一個(gè)具體的輸入字符和狀態(tài)的定義。它的作用在于使FAxx狀態(tài)定義更加簡潔。得到結(jié)論：在今后描述FA時(shí)，應(yīng)該根據(jù)具體的情況，使用適當(dāng)?shù)姆椒ā?******************************************************************************5．試區(qū)別FA中的陷阱狀態(tài)和不可達(dá)狀態(tài)。（xx賢珺02282047）解：⑴陷阱狀態(tài)（課本97頁）：指在其它狀態(tài)下發(fā)現(xiàn)輸入串不可能是該FA所識別的句子時(shí)所進(jìn)入的狀態(tài)。FA一旦進(jìn)入該狀態(tài)，就無法離開，并在此狀態(tài)下，讀完輸入串中剩余的字符。⑵不可達(dá)狀態(tài)（課本108頁）：指從FA的開始狀態(tài)出發(fā)，不可能到達(dá)的狀態(tài)。就FA的狀態(tài)轉(zhuǎn)移圖來說，就是不存在從開始狀態(tài)對應(yīng)的頂點(diǎn)出發(fā)，到達(dá)該狀態(tài)對應(yīng)頂點(diǎn)的路徑。⑶從兩者的定義可見：相對于不可達(dá)狀態(tài)來說，陷阱狀態(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)。******************************************************************************注：此題目有問題，可以將題設(shè)改為：xxx0和1個(gè)數(shù)相等且交替出現(xiàn)6．證明：題目有不嚴(yán)密之處，圖xx給出DFA與題目xx的語言L（M）={x|xx{0，1}+且xxx0的個(gè)數(shù)和1的個(gè)數(shù)相等}不完全對應(yīng)，首先圖xx的DFA可接受空字符串，而L（M）不接受，其次，對于有些句子，例如1100，L（M）可以接受，但DFA不接受（1）根據(jù)圖中的DFA可看出，右下角的狀態(tài)為陷阱狀態(tài)，所以去除陷阱狀態(tài)（2）由DFA可構(gòu)造出與其對應(yīng)的右線性文法：（xx02282083）由此可以看出該文法接受的語言為L={(10|01)*},顯然01或10分別是作為整體出現(xiàn)的，所以L(M)xx0和1的個(gè)數(shù)相等。******************************************************************************7．設(shè)DFAM=，證明：對于注：采用歸納證明的思路證明：(周期律

02282067)首先對y歸納，對任意x來說，|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定義，故原式成立，同理可證，對任意的y來說，結(jié)論也是成立的。綜上所述，原式得證*******************************************************************************8．證明:對于任意的DFAM1=(Q,Σ,δ,q0,F1)存在DFAM2=(Q,Σ,δ,q0,F2),（xx02282075）使得L(M2)=Σ*—L（M1）。證明：（1）構(gòu)造M2。設(shè)DFAM1=(Q,Σ,δ,q0,F1)取DFAM2=(Q,Σ,δ,q0,Q—F1)（2）證明L(M2)=Σ*—L（M1）對任意xΣ*xL(M2)=Σ*—L（M1）δ(q,x)Q—F1δ（q,x）Q并且δ（q,x）F1xΣ*并且xL(M1)xΣ*—L（M1）*******************************************************************************9.對于任意的DFAM1=(Q1,∑,δ1,q01,F1),請構(gòu)造DFAM1=(Q2,∑,δ2,q02,F2)，使得L(M1)=L(M2)T。其中L(M)T={x|xT∈L(M)}（xx02282072）構(gòu)造ε-NFAM使得L(M)=L(M1)取ε-NFAM=(Q,∑,δ,q0,{q01})其中:Q=Q1∪{q0},q0Q1對于q,p∈Q1,a∈∑,如果δ1(q,a)=p,q∈δ(p,a)δ(q0,ε)=F1證明：L(M)=L(M1)T對x=a2…am∈L(M)q2…am├qfa2…am├a1q2…am├a2q2…am├…├a2…qm-1am├a2…amq01其中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因此q01amam-1…a1├amqm-1am-1…a1├amam-1…q1├amam-1…a2q1├amam-1…a1qf因此amam-1…a1∈L(M1)即xT∈L(M1)同理可證對于x=a2…am∈L(M1)xT=amam-1…a1∈L(M1)L(M)=L(M1)T得證（3）將ε-NFAM確定化首先構(gòu)造與ε-NFAM=(Q,∑,δ,q0,{q01})等價(jià)的NFAM3=(Q,∑,δ2,q0,{q01})其中對于（q,a）∈Q*∑δ2(q,a)=δ^(q,a)然后按照以前學(xué)過的方法構(gòu)造與NFAM3=(Q,∑,δ2,q0,{q01})等價(jià)的DFAM1=(Q1,∑,δ1,[q0],F1)其中：Q1=2QF1={q01}δ1([q1,q2,…,qn],a)=[p1,p2,…,pn]當(dāng)且僅當(dāng)δ2({q1,q2,…,qn},a)={p1,p2,…,pn}*******************************************************************************注：此題（10題）xx、xx所做完全一樣！！10、構(gòu)造識別下列語言的NFA（xx02282091）這是最基本的單元，其他的可以通過這個(gè)逐級構(gòu)造出來，以滿足題目要求。*******************************************************************************11.根據(jù)給定的NFA，構(gòu)造與之等價(jià)的DFA.（xx02282090）（1）NFAM1的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9狀態(tài)說明狀態(tài)輸入字符012開始狀態(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)說明狀態(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]圖3-9所示NFA等價(jià)的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]圖3-10所示NFA等價(jià)的DFA****************************************************************************12．證明對于任意的NFA，存在與之等價(jià)的NFA,該NFA最多只有一個(gè)終止?fàn)顟B(tài)（xx02282083）證明：對于任意的NFAM=(Q，∑，δ，q0，F(xiàn))，我們?nèi)绻軜?gòu)造出一個(gè)只有一個(gè)終止?fàn)顟B(tài)的NFA，并且與之等價(jià)，即可證明上面的定理而對于任意的NFA存在下面兩種情況：(1)終止?fàn)顟B(tài)只有一個(gè)(2)終止?fàn)顟B(tài)有多個(gè)要構(gòu)造這個(gè)等價(jià)的NFA,可以采用如下方法：對(1)無需變化，該NFA即為滿足條件的NFA對(2)可以在該NFA的狀態(tài)圖上添加一個(gè)新的終止?fàn)顟B(tài)，并將原來的多個(gè)終止?fàn)顟B(tài)所連接的弧復(fù)制到該狀態(tài)上，此時(shí)這個(gè)終止?fàn)顟B(tài)為新狀態(tài)圖中唯一的終止?fàn)顟B(tài)，且這個(gè)新的NFA與原

NFA等價(jià)，滿足條件我們總能構(gòu)造出這樣的NFA因此對于任意的NFA，存在與之等價(jià)的NFA,該NFA最多只有一個(gè)終止?fàn)顟B(tài)*******************************************************************************13．試給出一個(gè)構(gòu)造方法，對于任意的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)。為了證明，我們在的基礎(chǔ)上，其中，即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然則又因?yàn)楣?，故同理容易證明故，又因?yàn)?，故可知，?gòu)造的是符合要求的。*******************************************************************************14．構(gòu)造識別下列語言的ε-NFA。(xx賢珺02282047)⑴{x│x∈{0,1}+且x中含形如10110的子串}∪{x│x∈{0,1}+和x的倒數(shù)第10個(gè)字符是1，且以01結(jié)尾}。解：得到的ε-NFA如下所示：εε0,10,11110000S00,110,10,10,10,10,10,10,101ε0,100,11110000S00,110,10,10,10,10,10,10,101εεε⑵{x│x∈{0,1}+且x中含形如10110的子串}{x│x∈{0,1}+和x的倒數(shù)第10個(gè)字符是1，且以01結(jié)尾}解：得到的ε-NFA如下所示：0,10,10,111100000,110,10,10,110,10,10,1110,101Sε⑶{x│x∈{0,1}+且x中不含形如10110的子串}∪{x│x∈{0,1}+且x以0開頭以1結(jié)尾}。解：關(guān)鍵是構(gòu)造第一個(gè)FA，方法是設(shè)置5個(gè)狀態(tài)：q0：表示開始狀態(tài)，以及連續(xù)出現(xiàn)了兩個(gè)以上的0時(shí)所進(jìn)入的狀態(tài)。q1:表示q0狀態(tài)下接受到1時(shí)（即開始狀態(tài)或2個(gè)以上的0后輸入1時(shí)）所進(jìn)入的狀態(tài)。q2:表示q1狀態(tài)下接受到0時(shí)（即開始狀態(tài)或2個(gè)以上的0后輸入10時(shí)）所進(jìn)入的狀態(tài)。q3:表示q2狀態(tài)下接受到1時(shí)（即開始狀態(tài)或2個(gè)以上的0后輸入101時(shí)）所進(jìn)入的狀態(tài)。q4:表示q3狀態(tài)下接受到1時(shí)（即開始狀態(tài)或2個(gè)以上的0后輸入1011時(shí)）所進(jìn)入的狀態(tài)。故得到的ε-NFA如下所示：SSεε0110q1q0q2q3q410110εεεεεF00,11s0s1s2ε1⑷{x│x∈{0,1}+且x中不含形如00的子串}{x│x∈{0,1}+且x中不含形如11的子串}。解：得到的ε-NFA如下所示：110110,1ε01000,1S另外，本題可以構(gòu)造DFA如下（其中qt為陷阱狀態(tài)）：qq0q10q21S111q40q5100q3001q601qt0,1⑸{x│x∈{0,1}+且x中不含形如00的子串}∩{x│x∈{0,1}+且x中不含形如11的子串}。解：由于xxx既不含形如00的子串，又不含形如11的子串，故xxx只能是01相間的串。所以，得到的ε-NFA如下所示：εεε01εεεε1ε0εS另外，本題可以構(gòu)造DFA如下（其中q+為陷阱狀態(tài)）：SS0101010110qt0,1*******************************************************************************15．（1）根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù)，起始狀態(tài)q0的閉包為-CLOSURE（q0）={q0,q2}。由此對以后每輸入一個(gè)字符后得到的新狀態(tài)再做閉包，得到下表：（xx02282085）狀態(tài)01{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)01{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)注：本題沒有必要按照NFA到DFA轉(zhuǎn)化的方法來做，而且從-NFA到NFA轉(zhuǎn)化時(shí)狀態(tài)沒有必要改變，可以完全采用-NFA中的狀態(tài)如（1）狀態(tài)01q0(開始狀態(tài)){q0,q1，q2q3}{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)01q0(開始狀態(tài)){q1q2q3，}{q0,q1，q2，q3}q1{q2}{q1，q2}q2{，q2，q3}{q0,q2，q3}q3（終止?fàn)顟B(tài)）空{(diào)q0}*******************************************************************************證明對于的FAM1=(Q1,∑1,δ1,q01,F1)，F(xiàn)AM1=(Q2,∑2,δ2,q02,F2)，存在FAM，使得L(M)=L(M1)∪L(M2)（xx02282072）證明：不妨設(shè)Q1與Q2的交集為空構(gòu)造M=（Q1∪Q2∪{q0},∑,δ,q0,F）其中：1）∑=∑1∪∑=F1∪F22)δ(q0,ε)={q01,q02}對于q∈Q1,a∈∑1δ(q,a)=δ1(q,a)對于q∈Q2,a∈∑2,δ(q,a)=δ2(q,a)證明：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）∈FF=F1∪F2則δ(q01,x)=δ1(q01,x)∈F1因此x∈L(M1)如果是δ(q02,x)因?yàn)镼1與Q2的交集為空而且δ（q0,x）∈FF=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)*******************************************************************************（xxxx02282084）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}要證，只需證明，證明2)再證明*******************************************************************************（xx02282090）*****************************************************************************19、總結(jié)本章定義的所有FA，歸納出它們的特點(diǎn)，指出它們之間的差別。（xx02282091）本章學(xué)習(xí)了DFA，NFA，ε-NFA，2DFA和2NFA所有的FA都是一個(gè)五元組M=（Q，Σ，δ，q0，F(xiàn)）最大的區(qū)別就是狀態(tài)轉(zhuǎn)移函數(shù)δ對于DFA，字母表中的每個(gè)字母都有唯一確定的狀態(tài)轉(zhuǎn)移函數(shù)。也就是說δ（q，a）∈Q×Σ，q∈Q，a∈Σ只有唯一確定的狀態(tài)。對于NFA，對于字母表中的每個(gè)輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對于ε串，是一個(gè)到自身的移動(dòng)。對于ε-NFA，是指在不接受任何字符的情況下，自動(dòng)機(jī)的狀態(tài)可以發(fā)身轉(zhuǎn)移。對于2DFA，對于字母表中的每個(gè)字符，對于每個(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è)。對于2NFA，與2DFA相似，但是并不是對于字母表中的每個(gè)輸入字符都有轉(zhuǎn)移函數(shù)，2NFA與2DFA的區(qū)別類似于DFA與NFA的區(qū)別。*******************************************************************************20構(gòu)造如圖3-20所個(gè)的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)的左線性文法。(xx賢珺02282047)⑴圖形如下所示00010,1101q0q1q2q3S解：設(shè)q0、q1、q2、q3所對應(yīng)的字符分別為A、B、C、G。由于q2為不可達(dá)狀態(tài)，故先去掉該狀態(tài)。得到該圖所對應(yīng)的左線性文法為：G→A1│B1│1B→G0│G1│A0│0A→B0 ⑵圖形如下所示：qq0q1q2q3S0110100,101解：圖中有多個(gè)終結(jié)狀態(tài)，為方便起見，增加一個(gè)終結(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→C0C→B0│A1│1B→C1│D0│D1│A0│0A→B1*******************************************************************************22.根據(jù)下列給定文法，構(gòu)造相應(yīng)的FA。（xxxx02282068）(1)文法G1的產(chǎn)生式集合如下：G1:S→a|AaA→a|Aa|cA|BbB→a|b|c|aB|Bb|Cb(2)文法G2的產(chǎn)生式集合如下：G2:S→a|AaA→a|Aa|Ac|BbB→a|b|c|Ba|Bb|Bc解答:文法G1對應(yīng)的FA如下所示文法G2對應(yīng)的FA如下所示******************************************************************************23.FAM的移動(dòng)函數(shù)定義如下:（xx02282075）δ(q0,3)={q0}δ(q0,1)={q1}δ(q1,0)={q2}δ(q1,1)={q3}δ(q2,0)={q2}δ(q3,1)={q3}其中,q2,q3為終態(tài).M是DFA嗎?為什么?不是,因?yàn)椴⒉皇撬械臓顟B(tài),在接收一個(gè)字母表中的字符時(shí)會有一個(gè)狀態(tài)與之對應(yīng).畫出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖給出你所畫出的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*}求正則方法G,使L(G)=L(M)q0→3q0|1q1

q1→0q2|1q3

q2→0|0q2

q3→1|1q3*****************************************************************