第4 章作業(yè)答案.doc

第4章 詞法分析1.構(gòu)造下列正規(guī)式相應(yīng)的DFA.（） 1(0|1)*101答案：1) 先構(gòu)造NFA：11100/1AXBYC2)將NFA 確定化:Q 01X XA AA AA AA,B BA,B BA,C CA,B BA,C CA AA,B,Y YA,B,Y Y A,C CA,B B3) DFA:2. 已知NFA（x,y,z,0,1,M,x,z），其中：M(x,0)=z，M(y,0)=x,y，,M(z,0)=x,z，M(x,1)=x，M(y,1)=，M(z,1)=y，構(gòu)造相應(yīng)的DFA。答案：1) 根據(jù)題中映射，得如下NFA轉(zhuǎn)換矩陣：01xzxyx,yzx,zy2) 轉(zhuǎn)成NFA（這步可省）：3) 確定化： Q 01x Xz Ax Xz Ax,z By Cx,z Bx,z Bx,y Ey Cx,y Ex,y Ex,y,z Fx Xx,y,z Fx,y,z Fx,y E4. 將下圖的（a）和（b）分別確定化和最小化：（a） 確定化： Q ab0 00,1 11 20,1 10,1 11 21 20 0最小化：0 0,1 2因?yàn)椋?,1a=1 0,1b=2 不能拆分1 0,1 20,1二狀態(tài)合并，得（b） 因?yàn)樽詣?dòng)機(jī)（b）已確定化，所以只做最小化：0 1,2,3,4,5 0因?yàn)?4a=0 1,2,3,5a=1,2,3, 51 1,2,3,5 4 0因?yàn)?,5b=4 2,3b=2,32 1, 5 2,3 4 0因?yàn)?2a=1 3a=33 1, 5 2 3 4 0因?yàn)?1, 5a=1,5 1, 5b=4 不能拆分4 1, 5 2 3 4 0將 1, 5合并得：5.構(gòu)造一個(gè)DFA，它接收=0,1上所有滿足如下條件的字符串：每個(gè)1 都有0 直接跟在右邊。并給出該語(yǔ)言的正規(guī)式。答案：1)按題意相應(yīng)的正規(guī)表達(dá)式可為(0 | 10)*， 構(gòu)造相應(yīng)的DFA：2)將DFA轉(zhuǎn)成右線性文法：S-A|A-0A|0|1BB-0A|08.給出下述文法所對(duì)應(yīng)的正規(guī)式：S0A|1BA1S|1B0S|0答案：將A、B 產(chǎn)生式的右部代入S 中,得：S=01S|01|10S|10=（01|10）S| 01|10所以：S= (01|10)* |01|1010.構(gòu)造下述文法GS的自動(dòng)機(jī)：S-A0A-A0|S1|0該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。該自動(dòng)機(jī)相應(yīng)的語(yǔ)言是什么？答案：1) 將題中左線性文法轉(zhuǎn)換為自動(dòng)機(jī)：因?yàn)槭亲缶€性文法，要增加一開(kāi)始狀態(tài)X，開(kāi)始符號(hào)S成終結(jié)狀態(tài)：2) 該自動(dòng)機(jī)為NFA，確定化： Q 01x XA AA AA,S BA,S BA,S BA A3) 該自動(dòng)機(jī)表達(dá)的語(yǔ)言用正規(guī)式表示為：00(0|10)*， 或：以00開(kāi)頭，0結(jié)尾，中間若有1，則1后一定跟0。附加題：已有NFA M=（S，A，B，F(xiàn)，0,1,f,S,F）,狀態(tài)圖如下圖所示，1 將此NFA轉(zhuǎn)化成規(guī)范DFA； 2 轉(zhuǎn)化成正規(guī)文法。 3. 列出它拒絕接受的2個(gè)字符串（不同字符開(kāi)頭） 答案：1. 確定化： Q 01S SA,F AA,F AA,F AA,B BA,B BA,F AA,B,F CA,B,F CA,F AA,B,F C此DFA已為最小化的DFA2. 轉(zhuǎn)化成右線性的正規(guī)文法S-0A|0A-0A|0|1BB-0A|0|1