版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、1第二章第二章2.3敘述由下列正規(guī)式描述的語言(a)0(0|1)0在字母表01上以0開頭和結(jié)尾的長度至少是2的01串(b)((ε|0)1)在字母表01上所有的01串包括空串(c)(0|1)0(0|1)(0|1)在字母表01上倒數(shù)第三位是0的01串(d)0101010在字母表01上含有3個1的01串(e)(00|11)((01|10)(00|11)(01|10)(00|11))在字母表01上含有偶數(shù)個0和偶數(shù)個1的01串2.4為下列語言寫
2、正規(guī)定義C語言的注釋,即以開始和以結(jié)束的任意字符串,但它的任何前綴(本身除外)不以結(jié)尾。[解答]other→a|b|…other指除了以外C語言中的其它字符other1→a|b|…other1指除了和以外C語言中的其它字符comment→other(other1other)(f)由偶數(shù)個0和偶數(shù)個1構(gòu)成的所有0和1的串。[解答]由題目分析可知,一個符號串由0和1組成,則0和1的個數(shù)只能有四種情況:x偶數(shù)個0和偶數(shù)個1(用狀態(tài)0表示);x
3、偶數(shù)個0和奇數(shù)個1(用狀態(tài)1表示);x奇數(shù)個0和偶數(shù)個1(用狀態(tài)2表示);x奇數(shù)個0和奇數(shù)個1(用狀態(tài)3表示);所以,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ù)個
4、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和偶數(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)
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))因為S0→ε所以由偶數(shù)個0和偶數(shù)個1構(gòu)成的所有0和1的串的正規(guī)定義為:S0→((00|11)|(01|10)(00|11)(01|10))(g)由偶數(shù)個0和奇數(shù)個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,輸入符號集合Σ=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ū)分,即等價。S5S6S7S8a=S5S7S3S1第四次劃分:S0S2S1S3S4S5S6S7S8S3S4a=S5S7第五次劃分:S0S2S1S3S4S5S6S7S8S5S6a=S5S7第六次劃分:S0S2S1S3S4S5S6S7S8S7S8a=S3S1第七次劃分:S0S2S1S3S4S5S6S7S8集合不可
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 編譯原理課后習(xí)題答案
- 編譯原理課后答案陳火旺
- 編譯原理第三版課后答案
- 編譯原理課后習(xí)題答案_清華大學(xué)_第二版
- 編譯原理及編譯程序構(gòu)造部分課后答案張莉楊海燕編著
- 編譯原理小題答案
- 編譯原理習(xí)題答案
- 編譯原理課后習(xí)題答案陳火旺+第三版
- 編譯原理習(xí)題及答案
- 編譯原理試題答案
- 編譯原理課后習(xí)題答案全集清華大學(xué)第二版
- 《編譯原理》西北工業(yè)大學(xué)第三版課后答案
- 編譯原理復(fù)習(xí)題答案
- 編譯原理作業(yè)參考答案
- 編譯原理模擬試卷及答案
- 編譯原理試題匯總+編譯原理期末試題8套含答案+大題集
- 編譯原理
- 編譯原理第五章答案
- 通信原理課后答案
- 編譯原理課后習(xí)題答案+清華大學(xué)出版社第二版
評論
0/150
提交評論