編譯原理課后答案.doc

第二章2.3敘述由下列正規(guī)式描述的語言21(a) 0(0|1)*0在字母表0,1上,以0開頭和結(jié)尾的長(zhǎng)度至少是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個(gè)1的01串(e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*在字母表0,1上,含有偶數(shù)個(gè)0和偶數(shù)個(gè)1的01串2.4為下列語言寫正規(guī)定義C語言的注釋，即以/*開始和以*/結(jié)束的任意字符串，但它的任何前綴（本身除外）不以*/結(jié)尾。解答othera|b|other指除了*以外C語言中的其它字符other1a|b|other1指除了*和/以外C語言中的其它字符comment/*other*(*other1other*)*/(f)由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有0和1的串。解答由題目分析可知，一個(gè)符號(hào)串由0和1組成，則0和1的個(gè)數(shù)只能有四種情況：x偶數(shù)個(gè)0和偶數(shù)個(gè)1（用狀態(tài)0表示）；x偶數(shù)個(gè)0和奇數(shù)個(gè)1（用狀態(tài)1表示）；x奇數(shù)個(gè)0和偶數(shù)個(gè)1（用狀態(tài)2表示）；x奇數(shù)個(gè)0和奇數(shù)個(gè)1（用狀態(tài)3表示）；所以，x狀態(tài)0（偶數(shù)個(gè)0和偶數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0和奇數(shù)個(gè)1（狀態(tài)1）x狀態(tài)0（偶數(shù)個(gè)0和偶數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0和偶數(shù)個(gè)1（狀態(tài)2）x狀態(tài)1（偶數(shù)個(gè)0和奇數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0和偶數(shù)個(gè)1（狀態(tài)0）x狀態(tài)1（偶數(shù)個(gè)0和奇數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0和奇數(shù)個(gè)1（狀態(tài)3）x狀態(tài)2（奇數(shù)個(gè)0和偶數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0和奇數(shù)個(gè)1（狀態(tài)3）x狀態(tài)2（奇數(shù)個(gè)0和偶數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0和偶數(shù)個(gè)1（狀態(tài)0）x狀態(tài)3（奇數(shù)個(gè)0和奇數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0和偶數(shù)個(gè)1（狀態(tài)2）x狀態(tài)3（奇數(shù)個(gè)0和奇數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0和奇數(shù)個(gè)1（狀態(tài)1）因?yàn)?，所求為由偶?shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有0和1的串，故狀態(tài)0既為初始狀態(tài)又為終結(jié)狀態(tài)，其狀態(tài)轉(zhuǎn)換圖：由此可以寫出其正規(guī)文法為：S01S1|0S2|S11S0|0S3|1S21S3|0S0|0S31S2|0S1在不考慮S0產(chǎn)生式的情況下，可以將文法變形為：S0=1S1+0S2S1=1S0+0S3+1S2=1S3+0S0+0S3=1S2+0S1所以：S0=(00|11)S0+(01|10)S3+11+00(1)S3=(00|11)S3+(01|10)S0+01+10(2)解(2)式得：S3=(00|11)*(01|10)S0+(01|10)代入(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)*(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)+因?yàn)镾0所以由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有0和1的串的正規(guī)定義為：S0(00|11)|(01|10)(00|11)*(01|10)*(g)由偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有0和1的串。解答此題目我們可以借鑒上題的結(jié)論來進(jìn)行處理。對(duì)于由偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有0和1的串，我們分情況討論：(1)若符號(hào)串首字符為0，則剩余字符串必然是奇數(shù)個(gè)0和奇數(shù)個(gè)1，因此我們必須在上題偶數(shù)個(gè)0和偶數(shù)個(gè)1的符號(hào)串基礎(chǔ)上再讀入10（紅色軌跡）或01（藍(lán)色軌跡），又因?yàn)樵?1和13的過程中可以進(jìn)行多次循環(huán)（紅色虛線軌跡），同理02和23（藍(lán)色虛線軌跡），所以還必須增加符號(hào)串(00|11)*，我們用S0表示偶數(shù)個(gè)0和偶數(shù)個(gè)1，用S表示偶數(shù)個(gè)0和奇數(shù)個(gè)1則其正規(guī)定義為：S0(00|11)*(01|10)S0S0(00|11)|(01|10)(00|11)*(01|10)*(2)若符號(hào)串首字符為1，則剩余字符串必然是偶數(shù)個(gè)0和偶數(shù)個(gè)1，其正規(guī)定義為：S1S0S0(00|11)|(01|10)(00|11)*(01|10)*綜合(1)和(2)可得，偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有0和1串其正規(guī)定義為：S0(00|11)*(01|10)S0|1S0S0(00|11)|(01|10)(00|11)*(01|10)*2.7(c) (|a)b*)*01a234567b58sfstartababbab: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)造最簡(jiǎn)的DFA(b)(a|b)*a(a|b)(a|b)(1)根據(jù)算法2.4構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA，如圖所示。(2)根據(jù)算法2.2（子集法）將NFA轉(zhuǎn)換成與之等價(jià)的DFA（確定化過程）初始狀態(tài)S0=-closure(0)=0,1,2,4,7標(biāo)記狀態(tài)S0S1=-closure(move(S0,a)=-closure(5,8)=1,2,4,5,6,7,8,9,11S2=-closure(move(S0,b)=-closure(3)=1,2,3,4,6,7標(biāo)記狀態(tài)S1S3=-closure(move(S1,a)=-closure(5,8,12)=1,2,4,5,6,7,8,9,11,12,13,14,16S4=-closure(move(S1,b)=-closure(3,10)=1,2,4,5,6,7,10,13,14,16標(biāo)記狀態(tài)S2S1=-closure(move(S2,a)=-closure(5,8)=1,2,4,5,6,7,8,9,11S2=-closure(move(S2,b)=-closure(3)=1,2,3,4,6,7標(biāo)記狀態(tài)S3S5=-closure(move(S3,a)=-closure(5,8,12,17)=1,2,4,5,6,7,8,9,11,12,13,14,16,17,18S6=-closure(move(S3,b)=-closure(3,10,15)=1,2,4,5,6,7,10,13,14,15,16,18標(biāo)記狀態(tài)S4S7=-closure(move(S4,a)=-closure(5,8,17)=1,2,4,5,6,7,8,9,11,17,18S8=-closure(move(S4,b)=-closure(3,15)=1,2,3,4,6,7,15,18標(biāo)記狀態(tài)S5S5=-closure(move(S5,a)=-closure(5,8,12,17)=1,2,4,5,6,7,8,9,11,12,13,14,16,17,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)S6S7=-closure(move(S6,a)=-closure(5,8,17)=1,2,4,5,6,7,8,9,11,17,18S8=-closure(move(S6,b)=-closure(3,15)=1,2,3,4,6,7,15,18標(biāo)記狀態(tài)S7S3=-closure(move(S7,a)=-closure(5,8,12)=1,2,4,5,6,7,8,9,11,12,13,14,16S4=-closure(move(S7,b)=-closure(3,10)=1,2,4,5,6,7,10,13,14,16標(biāo)記狀態(tài)S8S1=-closure(move(S8,a)=-closure(5,8)=1,2,4,5,6,7,8,9,11S2=-closure(move(S8,b)=-closure(3)=1,2,3,4,6,7由以上可知，確定化后的DFA的狀態(tài)集合S=S0,S1,S2,S3,S4,S5,S6,S7,S8，輸入符號(hào)集合=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,S1,S2,S3,S4S5,S6,S7,S8S0,S1,S2,S3,S4a=S1,S3,S1,S5,S7第二次劃分：S0,S1,S2S3,S4S5,S6,S7,S8S0,S1,S2a=S1,S3,S1第三次劃分：S0,S2S1S3,S4S5,S6,S7,S8S0,S2a=S1S0,S2b=S2S0,S2不可區(qū)分，即等價(jià)。S5,S6,S7,S8a=S5,S7,S3,S1第四次劃分：S0,S2S1S3,S4S5,S6S7,S8S3,S4a=S5,S7第五次劃分：S0,S2S1S3S4S5,S6S7,S8S5,S6a=S5,S7第六次劃分：S0,S2S1S3S4S5S6S7,S8S7,S8a=S3,S1第七次劃分：S0,S2S1S3S4S5S6S7S8集合不可再劃分，所以S0,S2等價(jià)，選取S0表示S0,S2，其狀態(tài)轉(zhuǎn)換圖，即題目所要求的最簡(jiǎn)DFA如下所示：第三章3.13.23.103.113.203.23第四章4.1 題目有點(diǎn)不同 方法一樣4.7（a)4.10（a)第六章6.36.56.126.236.9c語言函數(shù)f的定義如下： int f (int x,*py,*ppz) *ppz+=1;*py+=2;x+=3;return x+*py+*ppz; 變量a是一個(gè)指向b的指針；變量b是一個(gè)指向c的指針，而c是一個(gè)當(dāng)前值為4的整數(shù)變量。如果我們調(diào)用 f（a，b，c），返回值是什么？調(diào)用的順序不正確，應(yīng)該是f(c,b,a)才符合函數(shù)的定義，否則編譯是通不過的。除非調(diào)用時(shí)進(jìn)行強(qiáng)制轉(zhuǎn)換。如果強(qiáng)制轉(zhuǎn)換以后調(diào)用，f函數(shù)內(nèi)，ppz是形參，是個(gè)整數(shù)指針的指針，而ppz的實(shí)參是c，它的值就是4，指向的地址空間就是錯(cuò)誤的。py倒是可以，實(shí)參為b，指向c，*py的值就是c的值，為4。x的實(shí)參是a，實(shí)際上是個(gè)整數(shù)指針的指針，函數(shù)內(nèi)當(dāng)做整數(shù)來用，但是它的值是不確定的。如果按照f(c,b,a)的順序調(diào)用，*ppz+=1后，c=*b=*a=5；*py+=2后，c=*b=*a=7，x+=3后，x=7，而c=*b=*a=7，（這是因?yàn)閤為值傳遞，改變c沒有改變x，改變x也沒有改變c）最終返回的是7+7+7=21。第七章7.13 C語言的for語句有下列形式：For（e1;e2;e3）stmt 它和e1；