第3章習(xí)題解答

1、第3章習(xí)題解答1.構(gòu)造正規(guī)式1(0|1)*101 相應(yīng)的DFA. 答案轉(zhuǎn)化成DFA確定化01XAAAABABACABACAABYABYACAB重新命名，令 AB為B、AC為C、ABY為D01XAAABBCBCADDCB2.將以下圖確定化:答案01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQUZZZZ重新命名，令 VQ為 A QU為B、VZ為 C V為 D QUZ為E、Z為F。01SABACBBDECFFDFECEFFF轉(zhuǎn)化為DFA3.把以下圖最小化:答案(1) 初始分劃得n 0:終態(tài)組0，非終態(tài)組123,4,5對非終態(tài)組進行審查：1,2,3,4,5a 0,135而0,1,3,5既

2、不屬于0，也不屬于1,2,3,4,5/ 4 a _0，所以得新分劃(2) n 1： 0，4，1,2,3,5對1,2,3,5 進行審查：- 1,5 b 42,3 b 1,2,3,5，故得新分劃(3) n 2: 0 , 4 , 1, 5, 2,31, 5 a 1,52,3 a 1,3，故狀態(tài)2和狀態(tài)3不等價，得新分劃(3) n 3: 0 , 2 , 3 , 4 , 1, 5這是最后分劃了(4) 最小DFA4. 構(gòu)造一個DFA它接收 工=0,1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。并給出該語言的正規(guī)式和正規(guī)文法。答案按題意相應(yīng)的正規(guī)表達(dá)式是0*(100*)*0*構(gòu)造相應(yīng)的DFA首先構(gòu)

3、造NFA為用子集法確定化II0I1X,1,2 S 1,2 A 3 B 4,5,6,2,7,Y C 5,6,2,7,Y D1,2 A 1,2 A 4,5,6,2,7,Y C 5,6,2,7,Y D 5,6,2,7,Y D3 B3 B /3 B 3 BDFA可最小化，終態(tài)組為 G1=C, D,非終態(tài)組為 G2=S, A, B 對于G2分析：f(S,0)=A, f(A,0)=A,后繼狀態(tài)均屬于G2而f(B,0)=C,后繼狀態(tài)屬于G1將 G2分割成 G21=S, A, G22=B經(jīng)檢查DFA最小狀態(tài)集有三個，可用 S、B、D表示?；?按題意相應(yīng)的正規(guī)表達(dá)式是0*(0 | 10)*0*首先構(gòu)造NFA為用

4、子集法確定化II011S01X,0,1,3,Y0,1,3,Y:21230,1,3,Y0,1,3,Y222321,3,Y/341,3,Y1,3,Y2443可最小化，終態(tài)組為1,2,4，非終態(tài)組為3,1,2,40 1,2,4, 1,2,41- 3,所以1,2,4為等價狀態(tài)，可合并。5. 給出以下文法所對應(yīng)的正規(guī)式:S->0A|1BA->1S|1B->OS|O答案解方程組S的解：S=0A|1BA=1S|1B=OS|O將A、B產(chǎn)生式的右部代入 S中S=01S|01|10S|10=(01|10 ) S| (01|10)所以：S= (01|10)*(01|10)6. 為下邊所描述的串寫正

5、規(guī)式，字母表是a,b.a) 以ab結(jié)尾的所有串b) 包含偶數(shù)個b但不含a的所有串c) 包含偶數(shù)個b且含任意數(shù)目a的所有串d) 只包含一個a的所有串e) 包含ab子串的所有串f) 不包含ab子串的所有串答案注意正規(guī)式不唯一a) (a|b)*abb) (bb)*c) (a*ba*ba*)*d) b*ab*e) (a|b)*ab(a|b)*f) b*a*7. 請描述下面正規(guī)式定義的串.字母表S = 0 ，1.a) 0*(10+)*0*b) (0|1)*(00|11) (0|1)*c) 1(0|1)*0答案a) 每個1至少有一個0跟在后邊的串b) 所有含兩個相繼的0或兩個相繼的1的串c) 必須以1開頭

6、和0結(jié)尾的串8.構(gòu)造有窮自動機a)構(gòu)造個DFA接受字母表S =0,1上的以01結(jié)尾的所有串b)構(gòu)造個DFA接受字母表S =0, 1上的不包含01子串的所有串c)構(gòu)造個NFA接受字母表S =x,y上的正規(guī)式x(x|y)*x描述的集合d)構(gòu)造個NFA接受字母表S =a, b上的正規(guī)式(ab|a)*b+描述的集合并將其轉(zhuǎn)換為等價的DFA以及最小狀態(tài)DFA答案3)b)c)38DRhiDI A最小化的DFAd) N 卜 A:-786a t9.設(shè)有如下圖狀態(tài)轉(zhuǎn)換圖，求其對應(yīng)的正規(guī)表達(dá)式。答案可通過消結(jié)法得出正規(guī)式R=(01)*(00|1)(0|1)*|0)也可通過轉(zhuǎn)換為正那么文法，解方程得到正規(guī)式。10.正規(guī)式：(1)(a|b)*|aa)*b;(a| b)*b.試用有限自動機的等價性證明正規(guī)式(1)和 是等價的，并給出相應(yīng)的正規(guī)文法。分析根本思路是對兩個正規(guī)式，分別經(jīng)過確定化、最小化、化簡為兩個最小DFA如這兩個最小DFA一樣，也就證明了這兩個正規(guī)式是等價的。答案狀態(tài)轉(zhuǎn)換表1abX1241234124Y12341234124Y124Y1234124Y狀態(tài)轉(zhuǎn)換表2aB123223323由于2與3完全一樣，將兩者合并，即見下表ab123223而對正規(guī)式可畫NFA圖，如下