習題解答第3章xiwang

1、第四次作業(yè)：,P74 2、4、5、6,第4題 考察范圍：左線性文法 －> 狀態(tài)轉(zhuǎn)換圖P47第5題 考察范圍：右線性文法 －> 狀態(tài)轉(zhuǎn)換圖P48第6題 左線性文法 －> 狀態(tài)轉(zhuǎn)換圖， 狀態(tài)轉(zhuǎn)換圖 －>FA(DFA/NFA),P74 4. 畫出下列文法的狀態(tài)圖：Z：：=Be B：：=Af A：：=e|Ae 并使用該狀態(tài)圖檢查下列句子是否該文法的合法句

2、子：f, eeff, eefe。,由狀態(tài)圖可知只有eefe是該文法的合法句子。,左線性文法 －> 狀態(tài)轉(zhuǎn)換圖P47,P74 5. 設右線性文法G=({S, A, B}, {a, b}, S, P)，其中P組成如下：S：：=bA A：：=bB A：：=aA A：：=b B：：=a畫出該文法的狀態(tài)轉(zhuǎn)換圖。,,右線性文法 －> 狀態(tài)轉(zhuǎn)換圖P48,P74 6. 構(gòu)造下述文法G[Z]的自動機，該自動機

3、是確定的嗎？它相應的語言是什么？ Z：：=A0 A：：=A0|Z1|0,解：先畫出該文法狀態(tài)轉(zhuǎn)換圖：,其中M： M（S，0）={A} M（S，1）=øM（A，0）={A，Z} M（A，1）=øM（Z，0）=ø M（Z，1）={A}顯然該文法的自動機是非確定的；它相應的語言為：{0，1}上所有滿足以00開頭以0結(jié)尾

4、 且每個1必有0直接跟在其后的字符串的集合,NFA=（{S，A，Z}，{0，1}，M，{S}，{Z}）,左線性文法 －> 狀態(tài)轉(zhuǎn)換圖， 狀態(tài)轉(zhuǎn)換圖 －>FA(DFA/NFA) P57,第五次作業(yè)：,P74 7、8、9、10,第7題 具體字符串 －> 狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖－>正規(guī)文法（右線性）第8題 NFA－>DFA第9題 D

5、FA－>右線性文法 右線性文法－>左線性文法第10題 正規(guī)文法(右線性)－>DFA,P74 7. 構(gòu)造一個DFA，它接受{0，1}上所有滿足下述條件的字符串，其條件是：字符串中每個1都有0直接跟在右邊，然后，再構(gòu)造該語言的正規(guī)文法。,DFA=（{S，A，Z}，{0，1}，M，S，{Z}）其中M： M（S，0）=Z M（S，1）=

6、A M（A，0）=Z M（Z，0）=Z M（Z，1）=A該語言的正規(guī)文法G[Z]為：右線性文法：//S：：=0|1A|0Z 左線性文法：//S：：=0|A0|Z0 A：：=0|0Z A：：=1|Z1

7、 Z：：=0|1A|0Z Z：：=0|A0|Z0,0，00，10000，010，100… …,具體字符串 －> 狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖－>正規(guī)文法（右線性）,P74 8. 設 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} )，其中M定義如下：M (A, a)

8、 = {A, B} M (A, b) = {B} M (B, a) = ø M (B, b) = {A, B}請構(gòu)造相應確定有窮自動機(DFA) M’。解：構(gòu)造一個如下的自動機(DFA) M’， (DFA) M’={K, {a, b}, M’, S, Z}K的元素是[A] [B] [A, B]由于M（A, a）={A, B}，故有M’（[A], a）=[A, B]同樣 M’（[A]，b）=[B

9、]M’（[B]，a）= øM’（[B]，b）=[A，B]由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ø= {A，B}故 M’（[A，B]，a）= [A，B]由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B}故 M’（[A，B]，b）= [A，B]S=[A]，終態(tài)集Z={[A，B]，[B]}重新定義：令0=[A] 1=[B] 2=

10、[A, B]，則DFA如下所示：,,NFA－>DFAP59,可以進一步化簡，把M’的狀態(tài)分成終態(tài)組{1，2}和非終態(tài)組{0}由于{1，2}a={1，2}b={2},{1，2}，不能再劃分。至此，整個劃分含有兩組{1，2}{0}令狀態(tài)1代表{1，2}，化簡如圖：,P74 9. 設有窮自動機M = ({S, A, E}, {a, b, c}, M, S, {E})，其中M定義為 M (S, c) = A M

11、 (A, b) = A M (A, a) = E 請構(gòu)造一個左線性文法。解：方法一：先求右線性文法S→cA A→bA A→a | aE其左線性文法G=（VN, VT, P, S）VN={A, S} VT={a, b, c}P: A→c A→Ab S→Aa {E→aA實際上是多余的規(guī)則，應該去掉 }方法二：狀態(tài)轉(zhuǎn)換圖,DFA－>右線性文法 P61

12、 右線性文法－>左線性文法 P50,P74 10. 已知正規(guī)文法G = ({S, B, C}, {a, b, c}, P, S)，其中P內(nèi)包含如下產(chǎn)生式： S::=aS | aB ……①B::=bB | bC ……②C::=cC | c ……③ 請構(gòu)造一個等價的有窮自動機。解：M=({S, B, C, T}, {a, b, c}, M, {S}, {T})M (S,

13、a)=S M (S, a)=B M (S, b)=ø M (S, c)=øM (B, a)=ø M (B, b)=B M (B, b)=C M (B, c)=øM (C, a)=ø M (C, b)=ø M (C, c)=T M (C, c)=C,正規(guī)文法(右線性)－>FA P61,第六次作業(yè)：,P75－7611、15、1

14、6、18、19（1）、20（1）（3）,第11題 由正規(guī)式構(gòu)造DFA P65、66第15題 NFA構(gòu)造DFA P57（狀態(tài)圖）P65（轉(zhuǎn)換系統(tǒng)圖）第16、20題 兩個正規(guī)式的等級關系P63（若兩個正規(guī)式表達的正規(guī)集相等則兩者等價）第18題 正規(guī)文法構(gòu)造相應正規(guī)式 P63 第19題 由正規(guī)式構(gòu)造正規(guī)集P63,P74 15. 用兩種方法將(NFA) M = ({X, Y, Z}, {0, 1}, M

15、, {X}, {Z})，構(gòu)造相應的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},第一種方法：先畫出其狀態(tài)轉(zhuǎn)換圖，利用非子集法：,假設(DFA) M’=(K’, VT’, M’, S’, Z’)，其中K’={[X], [Y], [Z], [X,Y

16、], [X, Z], [Y, Z], [X, Y, Z]}，VT’={0, 1}，M’的規(guī)則如下表：,NFA構(gòu)造DFA P57（狀態(tài)圖）P65（轉(zhuǎn)換系統(tǒng)圖）,,其中[Y, Z]為不可到達狀態(tài)，應該刪去，所以S’={[X]}，Z’={[Z], [X, Z], [X, Y, Z]}，再進行化簡，發(fā)現(xiàn)4和6兩狀態(tài)等價，最后其DFA如下所示：,第二種方法：先構(gòu)造其對應的轉(zhuǎn)換系統(tǒng),由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示

17、：,,先化簡，分為非終態(tài)集 {2, 4, 5, 0} 和終態(tài)集 {6, 1, 3}，易于發(fā)現(xiàn)可劃分為{0, 2}，{1}，{3, 6}，{4}，{5}，其DFA如下所示：,P74 18. 根據(jù)下面正規(guī)文法構(gòu)造等價的正規(guī)表達式：S::=cC | a ……①A::=cA | aB ……②B::=aB | c ……③C::=aS | aA | bB | cC | a ……④解：由③式可得 B= aB +

18、 c → B=a*c 由②式可得 A= cA + aB → A= c*aa*c 由①式可得 S= cC + a 由④式可得 C= aS + aA + bB + cC + a → C= c*( aS + aA + bB + a) → C= c*( aS + ac*aa*c + ba*c + a) →

19、 S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) =

20、(cc*a)*( cc*( ac*aa*c | ba*c | a) | a) 另一種答案是S= c(ac | c)*( ac*aa*c | ba*c | aa | a) | a,正規(guī)文法構(gòu)造相應正規(guī)式 P63,P74 12. 將圖3.24非確定有窮自動機NFA確定化和最少化。,,解：設(DFA)M = {K, VT, M, S, Z}，其中，K={[0], [0, 1], [1]}，VT ={a, b}，M：M ([1]

21、, 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]},令[0, 1]=2，則其相應的狀態(tài)轉(zhuǎn)換圖為：,現(xiàn)在對該DFA進行化簡，先把狀態(tài)分為兩組：終態(tài)組 {0, 2} 和非終態(tài)組 {1}，易于發(fā)現(xiàn) {0, 2

22、}不可以繼續(xù)劃分，因此化簡后的狀態(tài)轉(zhuǎn)換圖如下：,,,P74 13. 構(gòu)造下列正規(guī)式的DFA（1）b(a|b)*bab 此題的與P74第11題基本一樣，見下,P74 11. 構(gòu)造下列正規(guī)式相應的DFA： （1）1(0|1)*101 【老書】解：先構(gòu)造該正規(guī)式的轉(zhuǎn)換系統(tǒng)：,由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集K={S, 1, 2, 3, 4, 5, Z}，狀態(tài)子集轉(zhuǎn)換矩陣如下表所示：,由正規(guī)式構(gòu)造D

23、FA P65、66,其對應的DFA狀態(tài)轉(zhuǎn)換圖為：,,現(xiàn)在對該DFA進行化簡，最終得到下列化簡后的狀態(tài)轉(zhuǎn)換圖（先將其分成兩組——終態(tài)組{5}和非終態(tài)組{0, 1, 2, 3, 4}，再根據(jù)是否可繼續(xù)劃分來確定最后的組數(shù)）：,P74 19. Σ＝{a, b}，寫出下列正規(guī)集：（1）(a | b)*(aa | bb)(a | b)*解：L((a | b)*(aa | bb)(a | b)*)

24、 = L((a | b)*) L((aa | bb)) L((a | b)*) =(L (a | b))* {aa, bb} (L (a | b))* = {a, b}*{aa, bb}{a, b}*,由正規(guī)式構(gòu)造正規(guī)集P63,精品課件！,精品課件！,P75 20. 證明下列關系式成立，其中A、B是任意正規(guī)表達式。（1）A | A = A （3）A* =

25、ε| AA*（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*；,P74 16. 已知e1= (a|b)*，e2=(a*b*)*，試證明e1= e2。證明：L(e1)=L((a|b)*)= (L (a|b))*= (L