編譯原理課后答案

1、第二章2.3敘述由下列正規(guī)式描述的語言21(a) 0(0|1)*0在字母表0, 1上,以0開頭和結(jié)尾的長度至少是2的01串(b) (|0)1*)*在字母表0, 1上,所有的01串,包括空串(c) (0|1)*0(0|1)(0|1)在字母表0, 1上,倒數(shù)第三位是0的01串(d) 0*10*10*10*在字母表0, 1上,含有3個1的01串(e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*在字母表0, 1上,含有偶數(shù)個0和偶數(shù)個1的01串2.4為下列語言寫正規(guī)定義 C語言的注釋，即以 /*

2、 開始和以 */ 結(jié)束的任意字符串，但它的任何前綴（本身除外）不以 */ 結(jié)尾。 解答  other  a | b |     other指除了*以外C語言中的其它字符  other1  a | b |     other1指除了*和/以外C語言中的其它字符  comment&#

3、160; /* other* (* * other1 other*)* * */   (f) 由偶數(shù)個0和偶數(shù)個1構(gòu)成的所有0和1的串。 解答 由題目分析可知，一個符號串由0和1組成，則0和1的個數(shù)只能有四種情況： x 偶數(shù)個0和偶數(shù)個1（用狀態(tài)0表示）； x 偶數(shù)個0和奇數(shù)個1（用狀態(tài)1表示）； x 奇數(shù)個0和偶數(shù)個1（用狀態(tài)2表示）； x 奇數(shù)個0和奇數(shù)個1（用狀態(tài)3表示）

4、； 所以， x 狀態(tài)0（偶數(shù)個0和偶數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和奇數(shù)個1（狀態(tài)1） x 狀態(tài)0（偶數(shù)個0和偶數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和偶數(shù)個1（狀態(tài)2） x 狀態(tài)1（偶數(shù)個0和奇數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和偶數(shù)個1（狀態(tài)0） x 狀態(tài)1（偶數(shù)個0和奇數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和奇數(shù)個1（狀態(tài)3） x 狀態(tài)2（奇數(shù)個0和偶數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和奇數(shù)個1（狀態(tài)3）x 狀態(tài)2（奇數(shù)個0

5、和偶數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和偶數(shù)個1（狀態(tài)0） x 狀態(tài)3（奇數(shù)個0和奇數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和偶數(shù)個1（狀態(tài)2） x 狀態(tài)3（奇數(shù)個0和奇數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和奇數(shù)個1（狀態(tài)1） 因為，所求為由偶數(shù)個0和偶數(shù)個1構(gòu)成的所有0和1的串，故狀態(tài)0既為初始狀態(tài)又為終結(jié)狀態(tài)，其狀態(tài)轉(zhuǎn)換圖： 由此可以寫出其正規(guī)文法為： S0  1S1 | 0S2 |   S1  1S

6、0 | 0S3 | 1   S2  1S3 | 0S0 | 0  S3  1S2 | 0S1在不考慮S0  產(chǎn)生式的情況下，可以將文法變形為： S0 = 1S1 + 0S2    S1 = 1S0 + 0S3 + 1 S2

7、0;= 1S3 + 0S0 + 0 S3 = 1S2 + 0S1    所以：     S0 = (00|11) S0 + (01|10) S3 + 11 + 00           (1)

8、0;S3 = (00|11) S3 + (01|10) S0 + 01 + 10           (2)    解(2)式得：     S3 = (00|11)* (01|10) S0 + (01|10)  

9、0; 代入(1)式得：     S0 = (00|11) S0 + (01|10) (00|11)*(01|10) S0 + (01|10) + (00|11)    => S0 = (00|11) + (01|10) (00|11)*(01|10)S0 + (01|10) (00|11)*(

10、01|10) + (00|11)    => S0 = (00|11)|(01|10) (00|11)*(01|10)*(00|11) + (01|10) (00|11)* (01|10)    => S0 = (00|11)|(01|10) (00|11)* (01|10)+    因為S0所以由偶數(shù)個0和偶數(shù)個1

11、構(gòu)成的所有0和1的串的正規(guī)定義為： S0  (00|11)|(01|10) (00|11)* (01|10)*  (g) 由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有0和1的串。 解答 此題目我們可以借鑒上題的結(jié)論來進(jìn)行處理。   對于由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有0和1的串，我們分情況討論： (1) 若符號串首字符為0，則剩余字符串必然是奇數(shù)個0和奇數(shù)個1，因此我們必須在上題偶數(shù)個0和偶數(shù)個1的符號串基礎(chǔ)上再讀入10（紅色軌跡）或01（藍(lán)色軌跡），又因為在0

12、1和13的過程中可以進(jìn)行多次循環(huán)（紅色虛線軌跡），同理02和23（藍(lán)色虛線軌跡），所以還必須增加符號串(00|11)*，我們用S0表示偶數(shù)個0和偶數(shù)個1，用S表示偶數(shù)個0和奇數(shù)個1則其正規(guī)定義為：S  0(00|11)*(01|10) S0    S0  (00|11)|(01|10) (00|11)* (01|10)*  (2) 若符號串首字符為1，則剩余字符串必然是偶數(shù)個0和偶數(shù)個1，其正規(guī)定義為：   S &#

13、160;1S0  S0  (00|11)|(01|10) (00|11)* (01|10)* 綜合(1)和(2)可得，偶數(shù)個0和奇數(shù)個1構(gòu)成的所有0和1串其正規(guī)定義為：   S  0(00|11)*(01|10) S0|1S0    S0  (00|11)|(01|10) (00|11)* (01|10)* 2.7(c) (|a)b*)*01a234567b58sfstarta

14、babbab:s->4->0->1->5->6->7->8->4->0->1->5->6->7->6->7->8->4->0->1->5->6->7->8->f2.12 為下列正規(guī)式構(gòu)造最簡的DFA (b) (a|b)* a (a|b) (a|b)  (1) 根據(jù)算法2.4構(gòu)造該正規(guī)式所對應(yīng)的NFA，如圖所示。 (2) 根據(jù)算法2.2（子集法）

15、將NFA轉(zhuǎn)換成與之等價的DFA（確定化過程） 初始狀態(tài) S0 = -closure(0) = 0, 1, 2, 4, 7 標(biāo)記狀態(tài)S0 S1 = -closure(move(S0, a) = -closure(5, 8) = 1, 2, 4, 5, 6, 7, 8, 9, 11 S2 = 

16、-closure(move(S0, b) = -closure(3) = 1, 2, 3, 4, 6, 7 標(biāo)記狀態(tài)S1 S3 = -closure(move(S1, a) = -closure(5, 8, 12) = 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13,

17、 14, 16  S4 = -closure(move(S1, b) = -closure(3, 10) = 1, 2, 4, 5, 6, 7, 10, 13, 14, 16 標(biāo)記狀態(tài)S2 S1 = -closure(move(S2, a) = -closure(5, 8) = 1,

18、60;2, 4, 5, 6, 7, 8, 9, 11 S2 = -closure(move(S2, b) = -closure(3) = 1, 2, 3, 4, 6, 7 標(biāo)記狀態(tài)S3 S5 = -closure(move(S3, a) = -closure(5, 8, 12, 17) =

19、 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18 S6 = -closure(move(S3, b) = -closure(3, 10, 15) = 1, 2, 4, 5, 6, 7, 10, 13, 14,

20、0;15, 16, 18 標(biāo)記狀態(tài)S4 S7 = -closure(move(S4, a) = -closure(5, 8, 17) = 1, 2, 4, 5, 6, 7, 8, 9, 11, 17, 18 S8 = -closure(move(S4, b) = -closure(3, 15)

21、60;= 1, 2, 3, 4, 6, 7, 15, 18 標(biāo)記狀態(tài)S5 S5 = -closure(move(S5, a) = -closure(5, 8, 12, 17) = 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 1

22、7, 18S6 = -closure(move(S5, b) = -closure(3, 10, 15) = 1, 2, 4, 5, 6, 7, 10, 13, 14, 15, 16, 18 標(biāo)記狀態(tài)S6 S7 = -closure(move(S6, a) = -closure(5, 8, 17)&

23、#160;= 1, 2, 4, 5, 6, 7, 8, 9, 11, 17, 18 S8 = -closure(move(S6, b) = -closure(3, 15) = 1, 2, 3, 4, 6, 7, 15, 18 標(biāo)記狀態(tài)S7 S3 = -closure(move(S7,

24、60;a) = -closure(5, 8, 12) = 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16 S4 = -closure(move(S7, b) = -closure(3, 10) = 1, 2, 4, 5, 6, 7, 

25、;10, 13, 14, 16 標(biāo)記狀態(tài)S8 S1 = -closure(move(S8, a) = -closure(5, 8) = 1, 2, 4, 5, 6, 7, 8, 9, 11 S2 = -closure(move(S8, b) = -closure(3) = 1, 2, 3,

26、 4, 6, 7 由以上可知，確定化后的DFA的狀態(tài)集合S = S0, S1, S2, S3, S4, S5, S6, S7, S8，輸入符號集合 = a, b，狀態(tài)轉(zhuǎn)換函數(shù)move如上，S0為開始狀態(tài)，接收狀態(tài)集合F = S5, S6, S7, S8，其狀態(tài)轉(zhuǎn)換圖如下所示：(3) 根據(jù)算法2.3過將DFA最小化   第一次劃分：S0,&

27、#160;S1, S2, S3, S4  S5, S6, S7, S8      S0, S1, S2, S3, S4a = S1, S3, S1, S5, S7 第二次劃分：S0, S1, S2  S3, S4   S5, S6, S7, 

28、;S8      S0, S1, S2a = S1, S3, S1   第三次劃分：S0, S2  S1 S3, S4  S5, S6, S7, S8  S0, S2a = S1 S0, S2b = S2  S0, S2不可區(qū)分，

29、即等價。S5, S6, S7, S8a = S5, S7, S3, S1  第四次劃分：S0, S2  S1 S3, S4  S5, S6   S7, S8      S3, S4a = S5, S7   第五次劃分：S0, S2 

30、; S1 S3   S4  S5, S6   S7, S8      S5, S6a = S5, S7   第六次劃分：S0, S2  S1 S3   S4  S5   S6   S7, S8   S7, S8a = S3, S1第七次