【正文】 )，其中P組成如下：S：：=bA A：：=bB A：：=aA A：：=b B：：=a畫出該文法的狀態(tài)轉(zhuǎn)換圖。 M（A，0）={A，Z} M（A，1）=248。 M（Z，1）={A}SZ’001A0ZS’εε顯然該文法的自動(dòng)機(jī)是非確定的；它相應(yīng)的語(yǔ)言為：{0，1}上所有滿足以00開(kāi)頭以0結(jié)尾且每個(gè)1必有0直接跟在其后的字符串的集合；也可以通過(guò)求解正規(guī)表達(dá)式得到A=0(0|01)*，Z=0(0|01)*0那么如何構(gòu)造其相應(yīng)的有窮自動(dòng)機(jī)呢？ 先構(gòu)造其轉(zhuǎn)換系統(tǒng)：根據(jù)其轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：(其中S’可以忽略，結(jié)果是一樣的)II0I1S0 1{S’, S}{A}Ф0 1 Ф{A}{A, Z, Z’}Ф1 2 Ф{A, Z, Z’}{A, Z, Z’}{A}2 2 11201000則其相應(yīng)的DFA為：P74 7. 構(gòu)造一個(gè)DFA，它接受{0，1}上所有滿足下述條件的字符串，其條件是：字符串中每個(gè)1都有0直接跟在右邊，然后，再構(gòu)造該語(yǔ)言的正規(guī)文法。 解(二)：可以先寫出該文法的正規(guī)表達(dá)式為(0 | 10)*，根據(jù)該正規(guī)式構(gòu)造轉(zhuǎn)換系統(tǒng)SZAεε01B0A01B0 對(duì)于該轉(zhuǎn)換系統(tǒng)可以采用子集法將其轉(zhuǎn)變?yōu)镈FA，再根據(jù)DFA寫出其正規(guī)文法；但是注意觀察后，發(fā)現(xiàn)開(kāi)始狀態(tài)S通過(guò)ε到達(dá)A狀態(tài)，可以直接刪去S狀態(tài)，由A狀態(tài)作為新的開(kāi)始狀態(tài)，同理，只有A狀態(tài)通過(guò)ε才能到達(dá)終止?fàn)顟B(tài)Z，因此可以刪去Z狀態(tài)，由A狀態(tài)作為終止?fàn)顟B(tài)?？僧嫵龌?jiǎn)后的轉(zhuǎn)換圖。 M (B, b) = {A, B}請(qǐng)構(gòu)造相應(yīng)確定有窮自動(dòng)機(jī)(DFA) M’。M’（[B]，b）=[A，B]由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U 248。解：先求右線性文法S→cA A→bA A→a | aE {A→aE實(shí)際上是多余的規(guī)則，應(yīng)該去掉}其左線性文法G=（VN, VT, P, S）VN = {A, S} VT = {a, b, c} 根據(jù)書上左右線性文法的轉(zhuǎn)換規(guī)則，得到P: A→c A→Ab S→Aa {E→Aa實(shí)際上是多余的規(guī)則，應(yīng)該去掉}畫出狀態(tài)轉(zhuǎn)換圖之后就非常清晰。解：M=({S, B, C, T}, {a, b, c}, M, {S}, {T})M (S, a)=S M (S, a)=B M (S, b)=248。M (B, a)=248。M (C, a)=248。 M (C, c)=T M (C, c)=C第六次作業(yè)：P74 11. 構(gòu)造下列正規(guī)式相應(yīng)的DFA： （1）1(0|1)*101 【老課本】解：先構(gòu)造該正規(guī)式的轉(zhuǎn)換系統(tǒng)：SZ1(0|1)*101S1534Z1101(0|1)*S1534Z11012εε01由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集K={S, 1, 2, 3, 4, 5, Z}，狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：II0I1K0 1{S}Ф{1, 2, 3}0Ф 1{1, 2, 3}{2, 3}{2, 3, 4}1 2 3{2, 3}{2, 3}{2, 3, 4}2 2 3{2, 3, 4}{2, 3, 5}{2, 3, 4}3 4 3{2, 3, 5}{2, 3}{2, 3, 4, Z}4 2 5{2, 3, 4, Z}{2, 3, 5}{2, 3, 4}5 4 3其對(duì)應(yīng)的DFA狀態(tài)轉(zhuǎn)換圖為：051123100114001100511, 23401111000現(xiàn)在對(duì)該DFA進(jìn)行化簡(jiǎn)，最終得到下列化簡(jiǎn)后的狀態(tài)轉(zhuǎn)換圖（先將其分成兩組——終態(tài)組{5}和非終態(tài)組{0, 1, 2, 3, 4}，再根據(jù)是否可繼續(xù)劃分來(lái)確定最后的組數(shù)）：（1）(0 | 11*0)* 【新課本】解：先構(gòu)造該正規(guī)式的轉(zhuǎn)換系統(tǒng)：SZ(0 | 11*0)*SZε10ε213ε10ε4SZε10ε11*0由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集K={S, 1, 2, 3, 4, Z}，狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：II0I1K0 1{S, 1, Z}{1, Z}{2, 3, 4}0 1 2{1, Z}{1, Z}{2, 3, 4}1 1 2{2, 3, 4}{1, Z}{3, 4}2 1 3{3, 4}{1, Z}{3, 4}3 1 3113000 010112由狀態(tài)子集轉(zhuǎn)換矩陣可知，狀態(tài)0和1是等價(jià)的，而狀態(tài)2和3是等價(jià)的，因此，合并等價(jià)狀態(tài)之后只剩下2個(gè)狀態(tài)，也即是最少狀態(tài)的DFA。10aa, ba NFA狀態(tài)轉(zhuǎn)換圖解：設(shè)(DFA)M = {K, VT, M, S, Z}，其中，K={[0], [0, 1], [1]}，VT ={a, b}，M：M ([1], a) =[0] M ([1], b) =Ф M ([0, 1], a) =[0, 1] M ([0, 1], b) =[1]M ([0], a) =[0, 1] M ([0], b) =[1]S=[1]，Z={[0], [0, 1]}10abaa2b令[0, 1]=2，則其相應(yīng)的狀態(tài)轉(zhuǎn)換圖為：現(xiàn)在對(duì)該DFA進(jìn)行化簡(jiǎn)，先把狀態(tài)分為兩組：終態(tài)組 {0, 2} 和非終態(tài)組 {1}，易于發(fā)現(xiàn) {0, 2}不可以繼續(xù)劃分，因此化簡(jiǎn)后的狀態(tài)轉(zhuǎn)換圖如下：10, 2abaP74 13. 構(gòu)造下列正規(guī)式的DFA： （1）b(a|b)*bab 此題的與P74第11題基本一樣，見(jiàn)上；P74 15. 用兩種方法將(NFA) M = ({X, Y, Z}, {0, 1}, M, {X}, {Z})，構(gòu)造相應(yīng)的DFA，其中：M (X, 0) = {Z} M (X, 1) = {X} M (Y, 0) = {X, Y}M (Y, 1) = Ф M (Z, 0) = {X, Z} M (Z, 1) = {Y}XZ101000Y0第一種方法：先畫出其狀態(tài)轉(zhuǎn)換圖，利用非子集法：假設(shè)(DFA) M’=(K’, VT’, M’, S’, Z’)，其中K’={[X], [Y], [Z], [X,Y], [X, Z], [Y, Z], [X, Y, Z]}，VT’={0, 1}，M’的規(guī)則如下表：II0I1K0 1[X][Z][X]0 2 0[Y][X, Y]Ф1 3 Ф[Z][X, Z][Y]2 4 1[X, Y][X, Y, Z][X]3 6 0[X, Z][X, Z][X, Y]4 4 3[Y, Z][X, Y, Z][Y]5 6 1[X, Y, Z][X, Y, Z][X, Y]6 6 3其中[Y, Z]為不可到達(dá)狀態(tài)，應(yīng)該刪去，所以S’={[X]}，Z’={[Z], [X, Z], [X, Y, Z]}，再進(jìn)行化簡(jiǎn)，發(fā)現(xiàn)4和6兩狀態(tài)等價(jià)，最后其DFA如下所示：0110001301124, 60XZ’101000Y0ZSεε第二種方法：先構(gòu)造其對(duì)應(yīng)的轉(zhuǎn)換系統(tǒng)：由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：II0I1K0 1{S, X}{Z, Z’}{X}0 1 2{Z, Z’}{X, Z, Z’}{Y}1 3 4{X}{Z, Z’}{X}2 1 2{X, Z, Z’}{X, Z, Z’}{X, Y}3 3 5{Y}{X, Y}Ф4 5 Ф{X, Y}{X, Y, Z, Z’}{X}5 6 2{X, Y, Z, Z’}{X, Y, Z, Z’}{X, Y}6 6 5141050001013, 610, 2先化簡(jiǎn)，分為非終態(tài)集 {2, 4, 5, 0} 和終態(tài)集 {6, 1, 3}，易于發(fā)現(xiàn)可劃分為{0, 2}，{1}，{3, 6}，{4}，{5}，其DFA如下所示：P74 16. 已知e1= (a|b)*，e2=(a*b*)*，試證明e1= e2。（1）A | A = A （3）A* = ε| AA* （4）(AB)*A = A(BA)*（1）解：L(A | A) = L(A)∪L(A) = L(A)，所以A | A = A；（3）解：L(A*) = (L(A))*，L(ε| AA*) ={ε}∪ L(A)L(A*) = (L(A))*，所以A* = ε| AA*；（4）解：(AB)*A = ((AB)0 ∪(AB)1∪(AB)2∪……)A = A∪ABA∪ABABA∪…… = A((BA)0 ∪(BA)1∪(BA)2∪……) = A(BA)*。解:（1）構(gòu)造FIRST集：FIRST(E’)={+, ε}FIRST(F’)={*, ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧}FIRST(T’)={ (，a，b, ε，∧}構(gòu)造FOLLOW 集：規(guī)則一?！蔉OLLOW(E) FOLLOW(E)={}規(guī)則二)∈FOLLOW(E) FOLLOE(E)={ )，}FIRST(E’){ε}FOLLOW(T) FOLLOW(T)={+}FIRST(T’){ε}FOLLOW(F) FOLLOW(F)={ (，a，b，∧}FIRST(F’){ε}FOLLOW(P) FOLLOW(P)={*}規(guī)則三FOLLOW(E) FOLLOW(E’) FOLLOW(E’)={ ，)}FOLLOW(E) FOLLOW(T) FOLLOW(T)={＋，＃，）}FOLLOW(T) FOLLOW(T’) FOLLOW(T’)= {＋，＃，）}FOLLOW(T) FOLLOW(F) FOLLOW(F)={ (，)，a，b，＋，＃，∧}FOLLOW(F) FOLLOW(F’) FOLLOW(F’)= { (，)，a，b，＋，＃，∧}FOLLOW(F) FOLLOW(P) FOLLOW(P)= { (，)，a，b，＋，＃，∧,*}最后結(jié)果為：FIRST(E’)={+, ε}FIRST(F’)={*, ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧}FIRST(T’)={ (，a，b, ε，∧)FOLLOE(E)={ ), ＃}FOLLOW(E’)={＃，)}FOLLOW(T)={＋，＃，）}FOLLOW(T’)= {＋，＃，）}FOLLOW(F)={ (，)，a，b，＋，＃，∧}FOLLOW(F’)={ (，)，a，b，＋，＃，∧}FOLLOW(P)= { (，)，a，b，＋，＃，∧,*}（2）證明該文法是LL（1）文法：證明：對(duì)于規(guī)則E’::=+E |ε，T’::=T |ε，F(xiàn)’::=*F’ |ε （僅有一邊能推出空串）有FIRST(+E)={+}∩FIRST(ε)= 248。 FIRST(*F’)={*}∩FIR