編譯原理第2章習(xí)題課.doc

1.構(gòu)造正規(guī)式的DFA。（1）1(0|1)*1010YXCADBE首先構(gòu)造NFA：0X11E1DCBA1NFA化為DFA：狀態(tài)轉(zhuǎn)換表：Q10X AABC BABC BBCD CBC DBCD CBCD CBCE EBC DBCD CBC DBCE EBCDY YBC DBCDY YBCD CBCE E1狀態(tài)轉(zhuǎn)換圖：0110110YABCDE10 初態(tài)010ABBCDCCEDCDEYDYCE化簡后得：01ABEY1101001C（2）(a|b)*(aa|bb)(a|b)*X12345Yaabbabab ？NFA化為DFA：QabX 1 21 2 31 2 41 2 31 2 3 5 Y1 2 4 1 2 41 2 31 2 4 5 Y1 2 3 5 Y1 2 3 5 Y1 2 4 Y1 2 4 5 Y1 2 3 Y1 2 4 5 Y1 2 4 Y1 2 3 Y1 2 4 5 Y1 2 3 Y1 2 3 5 Y1 2 4 Ya所以，DFA為：X123456ababbabbabaab化簡得：1XY2baababab01BCDYXA10（3）（0|11*0）*NFA到DFA：Q10X A Y XB C D AA Y BB C D AC D YA Y BA Y BB C D AA Y BC D YC D YA Y BABYX10100110化簡后得；XA10012.將下圖確定化和最小化。aa 0 1 a,b解: 首先取A=-CLOSURE(0)=0, NFA確定化后的狀態(tài)矩陣為:QabA00,11B0,10,11C10NFA確定化后的DFA為：aaABabbC將A,B 合并得:ab ACa3.構(gòu)造一個DFA，它接受=0，1上所有滿足如下條件的字符串，每個1都有0直接跟在后邊。解：按題意相應(yīng)的正規(guī)表達(dá)式是0*(0 | 10)*0* 構(gòu)造相應(yīng)的DFA，首先構(gòu)造NFA為 0 0 03 1 0 X Y 1 02 用子集法確定化II0I1S01X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y22/212342244333DFA為 01 02 1 1 0 13 4 04.給出NFA等價的正規(guī)式R。 方法一：首先將狀態(tài)圖轉(zhuǎn)化為BYCBAX11消去得0,1YCAX 11 消去其余結(jié)點、0，1YX（0|1）*11NFA等價的正規(guī)式為（0|1）*11方法二：NFA右線性文法正規(guī)式A0A|1A|1BB1CCA=0A+1A+1BB=1A=0A+1A+11A=(0+1)*11(0|1)*115.試證明正規(guī)式（a|b）*與正規(guī)式（a*|b*）*是等價的。 a證明：(1)Y1X正規(guī)式(a|b)*的NFA為 = b abX, 1,y1,y1,y1,y1,y1,yaA 其最簡DFA為 =b(2)正規(guī)式（a*|b*）*的 NFA為：3a其最簡化DFA為：aA2Y1 = X =bb DFA的狀態(tài)轉(zhuǎn)換表：abx,1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y由于這兩個正規(guī)式的最小DFA相同，所以正規(guī)式(a|b)*等價于正規(guī)式(a*|b*)*。6.設(shè)字母表=a,b,給出上的正規(guī)式R=b*ab(b|ab)*。（1） 試構(gòu)造狀態(tài)最小化的DFA M，使得L（M）=L（R）。（2） 求右線性文法G，使L（G）=L（M）。解: (1)構(gòu)造NFA:X123Ybab456abb (2)將其化為DFA,轉(zhuǎn)換矩陣為:QabX,1,2 13 21,2 33 24,5,Y 41,2 33 21,2 34,5,Y 46 55,Y 66 55,Y 65,Y 66 55,Y 6123456abbababbba再將其最小化得:XWYabbab（2）對應(yīng)的右線性文法G=（X,W,Y,a,b,P,X）P: XaW|bX WbY|b yaW|bY|b 3.8文法G單詞為：單詞-標(biāo)識符|整數(shù)標(biāo)識符-標(biāo)識符字母|標(biāo)識符數(shù)字|字母整數(shù)-數(shù)字|整數(shù)數(shù)字字母-A|B|C數(shù)字|-1|2|3（1）改寫文法G為G，使L(G)=L(G)。（2）給出相應(yīng)的有窮自動機(jī)。解：（1）令D代表單詞，I代表標(biāo)識符，Z代表整數(shù)，有G（D）：DI | Z IA | B | C | IA | IB | IC | I1 | I2 | I3Z1 | 2 | 3 | Z1 | Z2 | Z3(2) 左線性文法G所對應(yīng)的有窮自動機(jī)為：M=(S,D,I,Z,1,2,3,A,B,C,f,S,D)f: f(S,A)=I, f(S,B)=I, f(S,C)=I f(S,1)=Z f(S,2)=Z f(S,3)=Z f(I,A)=I f(I,B)=I f(I,C)=If(I,1)=I f(I,2)=I f(I,3)=I f(I, )=If(Z,1)=Z f(Z,2)=Z f(Z,3)=Z f(Z, )=D3.10給出下述文法所對應(yīng)的正規(guī)式。S0A|1BA1S|1B0S|0解: 相應(yīng)的正規(guī)式方程組為：S=0A+1B A=1S+1 B=0S+0 將，代入，得S=01S+01+10S+10 對使用求解規(guī)則，得 (01|10)* （01|10）為所求。3.4給出文法GS，構(gòu)造相應(yīng)最小的DFA。S-aS|bA|bA- aS 方法一：S=aS+bA+bA=aS S=aS+baS+b S=(a+ba)*b即：S=(a|ba)*b 正規(guī)式(a|ba)*b對應(yīng)的NFA：X1Y2ab3ab正規(guī)式(a|ba)*b對應(yīng)的DFA：QabX 1 2 X1 2 13Y Y1 2 11 2 13 Y Y3Y Y1 2 1X1Yaabab化簡后： XY1baa方法二：P43 右線性正規(guī)文法到有窮自動機(jī)的轉(zhuǎn)換。文法S-aS|bA|bA- aS 對應(yīng)的NFA為： M=(S,A,D,a,b,f,S,D)其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S 其NFA圖為：a S bAabDNFA確定化后的狀態(tài)矩陣為: Qab1SS A,D2A,D SNFA確定化后的DFA為：ab 12a3.5給出下述文法所對應(yīng)的正規(guī)式：S-aAA-bA+aB+bB-aA解：將文法改為：S=aA A=bA+aB+b B=aA將代入，得A=bA+aaA+b 將用求解規(guī)則，得A= (b|aa)*b ,帶入得，S= a(b|aa)*b,故文法所對應(yīng)的正規(guī)式為R= a(b|aa)*b。3.6給出與下圖等價的正規(guī)文法G。a AaBb Cb abDb答: 該有窮自動機(jī)為:M=(A,B,C,D,a,b,f,A,C,D)其中f(A,a)=B, f(A,b)=D, f(B,a)=, f(B,b)=C,f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D根據(jù)其轉(zhuǎn)換規(guī)則，與其等價的正規(guī)文法G為G=（A,B,C,D,a,b,P,A）,其中P : AaB|bD BbC CaA|bD| DaB|bD|3.12.解釋下列術(shù)語和概念：(1)確定有窮自動機(jī)答：一個確定有窮自動機(jī)M是一個五元組M=（Q，f，S，Z），其中：Q是一個有窮狀態(tài)集合，每一個元素稱為一個狀態(tài)；是一個有窮輸入字母表，每個元素稱為一個輸入字符；f是一個從Q*到Q的單值映射；f（qi,a）=qj (qi,qjQ,a)表示當(dāng)前狀態(tài)為qi，輸入字符為a時，自動機(jī)將轉(zhuǎn)換到下一個狀態(tài)qj,qj稱為 qi 的一個后繼狀態(tài)。我們說狀態(tài)轉(zhuǎn)換函數(shù)是單值函數(shù)，是指 f（qi,a） 惟一地確定了下一個要轉(zhuǎn)移的狀態(tài)，即每個狀態(tài)的所有輸出邊上標(biāo)記的輸入字符不同。SQ，是惟一的一個初態(tài)；Z 真包含于Q，是一個終態(tài)集。（2）非確定有窮自動機(jī)一個非確定有窮自動機(jī)M是一個五元組M=（Q，f，S，Z），其中：Q是一個有窮狀態(tài)集合，每一個元素稱為一個狀態(tài)；是一個有窮輸入字母表，每個元素稱為一個輸入字符；狀態(tài)轉(zhuǎn)換函數(shù)是一個多值函數(shù)。f（qi,a）=某些狀態(tài)的集合(qiQ)，表示不能由當(dāng)前狀態(tài)、當(dāng)前輸入字符惟一地確定下一個要轉(zhuǎn)移的狀態(tài)，即允許同一個狀態(tài)對同一輸入字符有不同的輸出邊。S 包含于 A，是非空初態(tài)集。Z 真包含于 Q，是一個終態(tài)集。（3）正規(guī)式和正規(guī)集有字母表=a1,a2,an，在字母表上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則來定義：（1）是是的正規(guī)式，它所表示的正規(guī)集是，即空集。（2）是上的正規(guī)式，它所表示的正規(guī)集僅含一空符號串，即 。（3）是上的一個正規(guī)式，它所表示的正規(guī)集是由單個符號ai 所組成，即ai。（4）e1和e2是是的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2),則e1 | e2是上的一個正規(guī)式，它所表示的正規(guī)集為 L(e1 | e2)=L(e1)L(e2).e1e2是上的一個正規(guī)式，它所表示的正規(guī)集為 L(e1e2)=L(e1)L(e2).(e1)*是上的一個正規(guī)式，它所表示的正規(guī)集為 L(e1)*)=L(e1)*.31構(gòu)造下列正規(guī)式相應(yīng)的DFA。(1) 1 ( 0 | 1)*101(2) ( a | b )*( aa | bb )( a | b )*(3) ( 0 | 1 )* | ( 11 )*(4) ( 0 | 11*0 )*32將下面圖(a)和(b)分別確定化和最小化.aa 0 1 a,b(a)b ba 02b3aaaabba145b（b）3.3構(gòu)造一個DFA，他接收=0，1上所有滿足如下條件的字符串，每個1都有0直接跟在右邊。3.4給出文法GS，構(gòu)造相應(yīng)最小的DFA。 SaS | bA | b AaS3.5給出下述文法所對應(yīng)的正規(guī)式：S-AaA-bA+aB+bB-aA3.6給出與下圖等價的正規(guī)文法G。a AaBb Cb abDb3.7給出與圖3.29中的NFA等價的正規(guī)式R。3.8 文法G單詞為：單詞標(biāo)識符| 整數(shù)標(biāo)識符標(biāo)識符字母| 標(biāo)識符數(shù)字|字母整數(shù)數(shù)字|整數(shù)數(shù)字字母 A | B | C數(shù)字1 | 2 | 3（1） 改寫文法G為G，使L(G)=L(G).（2） 給出相應(yīng)的有窮