編譯原理課后答案

1、1第二章第二章2.3敘述由下列正規(guī)式描述的語(yǔ)言(a)0(0|1)0在字母表01上以0開頭和結(jié)尾的長(zhǎng)度至少是2的01串(b)((ε|0)1)在字母表01上所有的01串包括空串(c)(0|1)0(0|1)(0|1)在字母表01上倒數(shù)第三位是0的01串(d)0101010在字母表01上含有3個(gè)1的01串(e)(00|11)((01|10)(00|11)(01|10)(00|11))在字母表01上含有偶數(shù)個(gè)0和偶數(shù)個(gè)1的01串2.4為下列語(yǔ)言寫

2、正規(guī)定義C語(yǔ)言的注釋，即以開始和以結(jié)束的任意字符串，但它的任何前綴（本身除外）不以結(jié)尾。［解答］other→a|b|…other指除了以外C語(yǔ)言中的其它字符other1→a|b|…other1指除了和以外C語(yǔ)言中的其它字符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

3、偶數(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è)

4、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)

5、又為終結(jié)狀態(tài)，其狀態(tài)轉(zhuǎn)換圖：由此可以寫出其正規(guī)文法為：S0→1S1|0S2|εS1→1S0|0S3|1S2→1S3|0S0|0S3→1S2|0S1在不考慮S0→ε產(chǎn)生式的情況下，可以將文法變形為：S0=1S10S2S1=1S00S31S2=1S30S00S3=1S20S1所以：S0=(00|11)S0(01|10)S31100(1)S3=(00|11)S3(01|10)S00110(2)解(2)式得：S3=(00|11)((01|10)

6、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)(0

7、0|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的串。3S4=εclosure(move(S1b))=εclosure(310)=12456710131416標(biāo)記狀態(tài)S2S1=εclosure(move(S2a))=εclosure(58)=1245678911S2=εclosur

8、e(move(S2b))=εclosure(3)=123467標(biāo)記狀態(tài)S3S5=εclosure(move(S3a))=εclosure(581217)=1245678911121314161718S6=εclosure(move(S3b))=εclosure(31015)=124567101314151618標(biāo)記狀態(tài)S4S7=εclosure(move(S4a))=εclosure(5817)=12456789111718S8=εcl

9、osure(move(S4b))=εclosure(315)=1234671518標(biāo)記狀態(tài)S5S5=εclosure(move(S5a))=εclosure(581217)=1245678911121314161718S6=εclosure(move(S5b))=εclosure(31015)=124567101314151618標(biāo)記狀態(tài)S6S7=εclosure(move(S6a))=εclosure(5817)=1245678911

10、1718S8=εclosure(move(S6b))=εclosure(315)=1234671518標(biāo)記狀態(tài)S7S3=εclosure(move(S7a))=εclosure(5812)=124567891112131416S4=εclosure(move(S7b))=εclosure(310)=12456710131416標(biāo)記狀態(tài)S8S1=εclosure(move(S8a))=εclosure(58)=1245678911S2=ε

11、closure(move(S8b))=εclosure(3)=123467由以上可知，確定化后的DFA的狀態(tài)集合S=S0S1S2S3S4S5S6S7S8，輸入符號(hào)集合Σ=ab，狀態(tài)轉(zhuǎn)換函數(shù)move如上，S0為開始狀態(tài)，接收狀態(tài)集合F=S5S6S7S8，其狀態(tài)轉(zhuǎn)換圖如下所示：(3)根據(jù)算法2.3過將DFA最小化第一次劃分：S0S1S2S3S4S5S6S7S8S0S1S2S3S4a=S1S3S1S5S7第二次劃分：S0S1S2S3S4S5S

12、6S7S8S0S1S2a=S1S3S1第三次劃分：S0S2S1S3S4S5S6S7S8S0S2a=S1S0S2b=S2S0S2不可區(qū)分，即等價(jià)。S5S6S7S8a=S5S7S3S1第四次劃分：S0S2S1S3S4S5S6S7S8S3S4a=S5S7第五次劃分：S0S2S1S3S4S5S6S7S8S5S6a=S5S7第六次劃分：S0S2S1S3S4S5S6S7S8S7S8a=S3S1第七次劃分：S0S2S1S3S4S5S6S7S8集合不可