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

第三章作業(yè)答案1已知DFA M1與M2如圖318所示。 (敖雪峰 02282068)(1) 請分別給出它們在處理字符串1011001的過程中經(jīng)過的狀態(tài)序列。(2) 請給出它們的形式描述。 圖318 兩個不同的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|x0，1+且x中不含00的串（設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進入陷阱狀態(tài)） （4） x|x0，1*且x中不含00的串（可接受空字符串，所以初始狀態(tài)也是接受狀態(tài)）（5）x|x0，1+且x中含形如10110的子串（6）x|x0，1+且x中不含形如10110的子串（設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進入陷阱狀態(tài)） （7）x|x0，1+且當(dāng)把x看成二進制時，x模5和3同余，要求當(dāng)x為0時，|x|=1,且x0時，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的等價類，q1：除以5余1的等價類,q2:除以5余2的等價類，q3:除以5余3的等價類，q4:除以5余4的等價類，接受狀態(tài)qt3. 狀態(tài)轉(zhuǎn)移表為狀態(tài)01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4 （8）x|x0，1+且x的第十個字符為1（設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個字符為0，進入陷阱狀態(tài)） （9）x|x0，1+且x以0開頭以1結(jié)尾（設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€字符為1時，進入陷阱狀態(tài)） （10）x|x0，1+且x中至少含有兩個1 （11）x|x0，1+且如果x以1結(jié)尾，則它的長度為偶數(shù)；如果x以0結(jié)尾，則它的長度為奇數(shù)可將0，1+的字符串分為4個等價類。q0： e的等價類，對應(yīng)的狀態(tài)為終止?fàn)顟B(tài)q1:x的長度為奇且以0結(jié)尾的等價類q2：x的長度為奇且以1結(jié)尾的等價類q3: x的長度為偶且以0結(jié)尾的等價類q4: x的長度為偶且以1結(jié)尾的等價類（12）x|x是十進制非負(fù)數(shù)（13）F（14）e*3 (1) （張友坤02282061）=0,1Set(q0)=x | x * (2)=0,1Set(q0)= Set(q1)=x | x + （3）=0,1Set(q0)= Set(q1)=x | x +并且x中不含形如00的子串 Set(q2)=x | x +并且x中不含形如00的子串 (4)=0,1Set(q0)=x | x *并且x中不含形如00的子串 Set(q1)=x | x *并且x中不含形如00的子串 (5)=0,1Set(q0)= x | x *,并且x0*或者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 | x0+Set(q2)=x | x *,并且x中不含形如10110的子串而且x中含有1Set(q3)=x | x *,并且x中不含形如10110的子串而且x中含有1(7)=0,1Set(qs)= Set(qe)= 0Set(q1)=x | x +,并且把x看成二進制數(shù)時，x% 5=1Set(q2)=x | x +,并且把x看成二進制數(shù)時，x% 5=2Set(q3)=x | x +,并且把x看成二進制數(shù)時，x% 5=3Set(q4)=x | x +,并且把x看成二進制數(shù)時，x% 5=4Set(q0)=x | x +,并且把x看成二進制數(shù)時，x% 5=0并且x不為0(8)M=Q, ,q0,FQ=q0,q1,q2,q10=0,1當(dāng)0=i=8時候，(q i,0)= ( q i,1)=q（i+1）( q 9,1)=q10(q 10,0)= ( q 10,1)=q10F= q 10Set(q0)= Set(q1)= 0,1Set(q2)=x | x +,并且|x|=2Set(q3)=x | x +,并且|x|=3Set(q4)=x | x +,并且|x|=4Set(q5)=x | x +,并且|x|=5Set(q6)=x | x +,并且|x|=6Set(q7)=x | x +,并且|x|=7Set(q8)=x | x +,并且|x|=8Set(q9)=x | x +,并且|x|=9Set(q10)=x | x +,并且x的第十個字符是1(9) M=Q, ,q0,FQ=q0,q1,q2 =0,1(q 0,0)=q1(q 1,0)= q1(q 1,1)= q2(q 2,1)= q2(q 2,0)= q1F= q 2Set(q0)= Set(q1)=x | x +,并且x以0開頭以0結(jié)尾 Set(q2)=x | x +,并且x以0開頭以1結(jié)尾 (10) M=Q, ,q0,FQ=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)= q2F= q 2Set(q0)= 0*Set(q1)=x | x +,并且x中只有一個1 Set(q2)=x | x +,并且x至少有倆個1(11) M=Q, ,q0,FQ=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)= q3F= q 0 ,q 1 ,q 2Set(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,FQ=q0,q1,q2,q3,q4=.,0,1,2,9F=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)=q4Set(q0)= Set(q1)=0 Set(q2)=十進制正整數(shù)Set(q3)=十進制非負(fù)整數(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）答：我認(rèn)為能夠直接用代替，因為在例3-6中，只是一種新的表示方法，用來表示狀態(tài)存儲的字符，這樣就省去了在中逐一給出每一個具體的輸入字符和狀態(tài)的定義。它的作用在于使FA中狀態(tài)定義更加簡潔。得到結(jié)論：在今后描述FA時，應(yīng)該根據(jù)具體的情況，使用適當(dāng)?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證明：題目有不嚴(yán)密之處，圖中給出DFA與題目中的語言L（M）=x|x x0，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定義,故原式成立。當(dāng)|y| = n時，假設(shè)原式成立，故當(dāng)|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,QF1) （2）證明L(M2)=*L（M1）對任意x*x L(M2)=*L（M1）(q,x)QF1（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|xTL(M) （褚穎娜 02282072）(1) 構(gòu)造-NFA M 使得 L(M)=L(M1) 取-NFA M=( Q, q0, q01) 其中:1) Q= Q1 q0, q0 Q1 2) 對于 q,pQ1,a,如果1(q,a)=p,q(p,a)3) (q0,)= F1(2) 證明：L(M)=L(M1)T對 x=a1 a2 amL(M)q0 a1 a2 amqf a1 a2 ama1 q1 a2 ama1 a2 q2 ama1 a2qm-1ama1 a2am q01其中qf(q0,), q1(qf, a1), q2(q1, a2),q01(qm-1, am) 并且qfF1則1(q01, am)= qm-1, 1(qm-1, am-1)= qm-2,1(q2, a2)= q11(q1, a1)= qf因此q01 am am-1a1am qm-1 am-1a1am am-1q2 a2 a1am am-1 a2 q1a1am am-1 a2 a1qf因此am am-1a1L(M1) 即 xTL(M1)同理可證對于 x=a1 a2 amL(M1) xT=am am-1a1L(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= q011(q1,q2 , ,qn,a)=p1,p2 ,pn 當(dāng)且僅當(dāng)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)輸入字符012開始狀態(tài)q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,q1q2,q1終止?fàn)顟B(tài)q3q3,q2q3 q0解答：狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0q0,q1q0,q2q0,q2q0,q1q0,q1,q3q0,q2q0,q2q0,q2q0,q1q0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2終止?fàn)顟B(tài)q0,q1,q3q0,q1,q2,q3q0, 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, q2圖3-9所示NFA等價的DFA（2）NFA M2 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-10狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0q1,q3q1q0 q1q2q1,q2q1q2q3,q2q0q2 終止?fàn)顟B(tài)q3q0 q3解答：狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0q1,q3q1q0q1,q3q2q0,q1,q2q1,q3q1q2q1,q2q1q2q2,q3q0q2q0,q1,q2q1,q2,q3q0, q1,q2q0,q1,q2q1,q2q2,q3q0,q1,q2q1, q2終止?fàn)顟B(tài)q2,q3q2,q3q0q2,q3終止?fàn)顟B(tài)q1,q2,q3q2,q3q0,q1,q2q1, q2,q3圖3-10所示NFA等價的DFA*12證明對于任意的NFA，存在與之等價的NFA,該NFA最多只有一個終止?fàn)顟B(tài) （劉鈺 02282083）證明：對于任意的NFA M=(Q，q0，F(xiàn)) ，我們?nèi)绻軜?gòu)造出一個只有一個終止?fàn)顟B(tài)的NFA，并且與之等價，即可證明上面的定理而對于任意的NFA存在下面兩種情況：(1)終止?fàn)顟B(tài)只有一個(2)終止?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)*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) xx0,1+ 且x中含形如10110的子串 xx0,1+ 和x的倒數(shù)第10個字符是1，且以01結(jié)尾 。 解：得到的-NFA如下所示：0, 10, 11110000S00, 110, 10, 10, 10, 10, 10, 10, 1010, 100, 11110000S00, 110, 10, 10, 10, 10, 10, 10, 101 xx0,1+ 且x中含形如10110的子串 xx0,1+ 和x的倒數(shù)第10個字符是1，且以01結(jié)尾 解：得到的-NFA如下所示：0, 10, 111100000, 110, 10, 10,1 10, 10, 10,1 110, 101S xx0,1+ 且x中不含形如10110的子串 xx0,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如下所示：S0110q1q0q2q3q410110F00, 11s0s1s21 xx0,1+ 且x中不含形如00的子串 xx0,1+ 且x中不含形如11的子串 。解：得到的-NFA如下所示：10110, 101000, 1S另外，本題可以構(gòu)造DFA如下（其中qt為陷阱狀態(tài)）：q0q10q21S111q40q5100q3001q601qt0, 1 xx0,1+ 且x中不含形如00的子串 xx0,1+ 且x中不含形如11的子串 。解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相間的串。所以，得到的-NFA如下所示：0110S 另外，本題可以構(gòu)造DFA如下（其中q+為陷阱狀態(tài)）：S0101010110qt0,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)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，q3q0= q0, q2，q1= q0, q1，q2，q2= q0, q1，q2，q3，因為q3為終止?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，q3q0= q1, q3，q1= q3，q2，q2= q0, q1，q2，q3，q3= q0, q1，q3，q4= q1，q2，q3因為各狀態(tài)均含有終止?fàn)顟B(tài)，所以q0, q1，q2，q3,q4均為終止?fàn)顟B(tài)注：本題沒有必要按照NFA到DFA轉(zhuǎn)化的方法來做，而且從e-NFA到NFA轉(zhuǎn)化時狀態(tài)沒有必要改變，可以完全采用e-NFA中的狀態(tài)如（1）狀態(tài)01q0(開始狀態(tài)) q0, q1，q2 q3 q0, q1，q2，q3q1 q0, q1，q2，q3 q1，q2，q3q2 q0, q1，q2，q3q1，q2，q3q3（終止?fàn)顟B(tài)） q0, q1，q2，q3 q0, q1，q2，q3(2) 狀態(tài)01q0(開始狀態(tài)) q1 q2 q3， q0, q1，q2，q3q1 q2 q1，q2q2，q2，q3 q0, q2，q3q3（終止?fàn)顟B(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=（Q1Q2 q0, q0,F）其中：1）=12 F= F1F22) (q0,)= q01 ,q02 對于 qQ1,a1(q, a)=1(q,a) 對于 qQ2,a2 ,(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)時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) 即xL(M)同理可證當(dāng)x L(M2)時xL(M)故L(M1)L(M2)L(M) 2) 再證明L(M)L(M1)L(M2)設(shè)xL(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= F1F2 則(q01 , x)= 1(q01 , x)F1 因此xL(M1)如果是(q02 , x) 因為Q1 與Q2的交集為空 而且（q0,x）F F= F1F2 則(q02 , x)= 2(q02 , x)F1 因此xL(M2)因此xL(M1)L(M2) L(M)L(M1)L(M2)得證因此L(M)= L(M1)L(M2)*（唐明珠 02282084）17 證明：對于任意的FA . 證明：令 ,其中的定義為： 1) 對qQ1-f1，a (q，a)=1(q，a)； 2) 對qQ2-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，qQ，a只有唯一確定的狀態(tài)。對于NFA，對于字母表中的每個輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對于串，是一個到自身的移動。對于-NFA，是指在不接受任何字符的情況下，自動機的狀態(tài)可以發(fā)身轉(zhuǎn)移。對于2DFA，對于字母表中的每個字符，對于每個狀態(tài)都有唯一的狀態(tài)轉(zhuǎn)移，即（q，a）Q，qQ，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，0P：對圖2：構(gòu)造文法G=（V，T，P，S），其中V=S，A，B，C，T=1，0P：*21構(gòu)造下圖所示DFA對應(yīng)的左線性文法。 (吳賢珺 02282047) 圖形如下所示0010, 1101q0q1q2q3S解：設(shè)q0、q1、q2、q3所對應(yīng)的字符分別為A、B、C、G。由于q2為不可達狀態(tài)，故先去掉該狀態(tài)。得到該圖所對應(yīng)的左線性文法為：GA1B11BG0G1A00AB0 圖形如下所示：q0q1q2q3S0110100, 101解：圖中有多個終結(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)的左線性文法為：GC0B0DC0CB0A11BC1D0D1A00AB1*22.根據(jù)下列給定文法，構(gòu)造相應(yīng)的FA。 （敖雪峰 02282068）(1) 文法G1的產(chǎn)生式集合如下： G1: Sa|AaAa|Aa|cA|BbBa|b|c|aB|Bb|Cb(2) 文法G2的產(chǎn)生式集合如下： G2: Sa|Aa Aa|Aa|Ac|Bb Ba|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)=qset(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)q03 q0|1 q1q10 q2|1 q3q20|0 q2q31|1 q3*24，總結(jié)規(guī)約與派生的對應(yīng)