編譯原理課后答案.doc

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