形式語言與自動機理論-第三章參考答案

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

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

NFA等價，滿足條件我們總能構造出這樣的NFA因此對于任意的NFA，存在與之等價的NFA,該NFA最多只有一個終止狀態(tài)*******************************************************************************13．試給出一個構造方法，對于任意的NFA，構造NFA，使得注：轉化成相應的DFA進行處理，然后可參考第8題的思路證明：(周期律

02282067)首先構造一個與NFA等價的DFA，根據定理3.1（P106），構造其中 在此基礎上，即取所有確定化后不是終結狀態(tài)的狀態(tài)為的終結狀態(tài)。為了證明，我們在的基礎上，其中，即所有確定化后的狀態(tài)都為終結狀態(tài)。顯然則又因為故，故同理容易證明故，又因為，故可知，構造的是符合要求的。*******************************************************************************14．構造識別下列語言的ε-NFA。(xx賢珺02282047)⑴{x│x∈{0,1}+且x中含形如10110的子串}∪{x│x∈{0,1}+和x的倒數第10個字符是1，且以01結尾}。解：得到的ε-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的倒數第10個字符是1，且以01結尾}解：得到的ε-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結尾}。解：關鍵是構造第一個FA，方法是設置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如下所示：SSεε0110q1q0q2q3q410110εεεεεF00,11s0s1s2ε1⑷{x│x∈{0,1}+且x中不含形如00的子串}{x│x∈{0,1}+且x中不含形如11的子串}。解：得到的ε-NFA如下所示：110110,1ε01000,1S另外，本題可以構造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另外，本題可以構造DFA如下（其中q+為陷阱狀態(tài)）：SS0101010110qt0,1*******************************************************************************15．（1）根據NFAM3的狀態(tài)轉移函數，起始狀態(tài)q0的閉包為-CLOSURE（q0）={q0,q2}。由此對以后每輸入一個字符后得到的新狀態(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}，因為q3為終止狀態(tài)，所以q2={q0,q1，q2，q3}為終止狀態(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}因為各狀態(tài)均含有終止狀態(tài)，所以q0,q1，q2，q3,q4均為終止狀態(tài)注：本題沒有必要按照NFA到DFA轉化的方法來做，而且從-NFA到NFA轉化時狀態(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（終止狀態(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（終止狀態(tài)）空{q0}*******************************************************************************證明對于的FAM1=(Q1,∑1,δ1,q01,F1)，F(xiàn)AM1=(Q2,∑2,δ2,q02,F2)，存在FAM，使得L(M)=L(M1)∪L(M2)（xx02282072）證明：不妨設Q1與Q2的交集為空構造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)設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)設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）∈FF=F1∪F2則δ(q01,x)=δ1(q01,x)∈F1因此x∈L(M1)如果是δ(q02,x)因為Q1與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、總結本章定義的所有FA，歸納出它們的特點，指出它們之間的差別。（xx02282091）本章學習了DFA，NFA，ε-NFA，2DFA和2NFA所有的FA都是一個五元組M=（Q，Σ，δ，q0，F(xiàn)）最大的區(qū)別就是狀態(tài)轉移函數δ對于DFA，字母表中的每個字母都有唯一確定的狀態(tài)轉移函數。也就是說δ（q，a）∈Q×Σ，q∈Q，a∈Σ只有唯一確定的狀態(tài)。對于NFA，對于字母表中的每個輸入字符可以有不同的狀態(tài)轉移，對于ε串，是一個到自身的移動。對于ε-NFA，是指在不接受任何字符的情況下，自動機的狀態(tài)可以發(fā)身轉移。對于2DFA，對于字母表中的每個字符，對于每個狀態(tài)都有唯一的狀態(tài)轉移，即δ（q，a）∈Q×Σ，q∈Q，a∈Σ只有唯一確定的狀態(tài)。與DFA不同的是，2DFA的讀頭可以在一次狀態(tài)轉移中不移動，或者回退一個，或者向下讀一個。對于2NFA，與2DFA相似，但是并不是對于字母表中的每個輸入字符都有轉移函數，2NFA與2DFA的區(qū)別類似于DFA與NFA的區(qū)別。*******************************************************************************20構造如圖3-20所個的DFA對應的右線性文法。(周期律

02282067)對圖1：構造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}P：對圖2：構造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}P：*******************************************************************************21．構造下圖所示DFA對應的左線性文法。(xx賢珺02282047)⑴圖形如下所示00010,1101q0q1q2q3S解：設q0、q1、q2、q3所對應的字符分別為A、B、C、G。由于q2為不可達狀態(tài)，故先去掉該狀態(tài)。得到該圖所對應的左線性文法為：G→A1│B1│1B→G0│G1│A0│0A→B0 ⑵圖形如下所示：qq0q1q2q3S0110100,101解：圖中有多個終結狀態(tài)，為方便起見，增加一個終結狀態(tài)（紅色表示），設該狀態(tài)所對應的字符為G。又設q0、q1、q2、q3所對應的字符分別為A、B、C、D。則該圖所對應的左線性文法為：G→C0│B0│εD→C0C→B0│A1│1B→C1│D0│D1│A0│0A→B1*******************************************************************************22.根據下列給定文法，構造相應的FA。（xxxx02282068）(1)文法G1的產生式集合如下：G1:S→a|AaA→a|Aa|cA|BbB→a|b|c|aB|Bb|Cb(2)文法G2的產生式集合如下：G2:S→a|AaA→a|Aa|Ac|BbB→a|b|c|Ba|Bb|Bc解答:文法G1對應的FA如下所示文法G2對應的FA如下所示******************************************************************************23.FAM的移動函數定義如下:（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嗎?為什么?不是,因為并不是所有的狀態(tài),在接收一個字母表中的字符時會有一個狀態(tài)與之對應.畫出相應的DFA的狀態(tài)轉移圖給出你所畫出的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*}求正則方法G,使L(G)=L(M)q0→3q0|1q1

q1→0q2|1q3

q2→0|0q2

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