第3章 作業(yè)及參考答案

《第3章 作業(yè)及參考答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《第3章 作業(yè)及參考答案（5頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1、針對(duì)DFA M1， (1)請(qǐng)給出在處理字符串1011001的過(guò)程中經(jīng)過(guò)的狀態(tài)序列。 解：經(jīng)過(guò)的狀態(tài)序列為：q0q3q1q3q2q3q1q3 (2)請(qǐng)給出形式描述。 爭(zhēng)議：M1的形式化還是接受過(guò)程的形式化？ 解：M1的形式描述為M1=({q0,q1,q2,q3},{0,1},δ, q0,{ q3}) 其中δ定義為： δ(q0,0)= q1，δ(q0,1)= q3 δ(q1,0)= q2，δ(q1,1)= q3 δ(q2,0)= q3，δ(q2,1)= q0 δ(q3,0)= q1，δ(q3,1)= q2 接受過(guò)程的形式化：q01011001├1q3011001├10q1

2、11001├101q31001├1011q2001├10110q301├101100q11├1011001q3 注意：談及自動(dòng)機(jī)形式化描述，一定是用五元組表示，將δ函數(shù)直接寫出來(lái) 2、構(gòu)造識(shí)別下列語(yǔ)言的DFA （要求寫出形式化描述，另外，寫出設(shè)計(jì)過(guò)程對(duì)理清你的思維更有益） (3) {x| x∈{0,1}+且x中不含形如00的子串} 1 0 0 1 qt qs q1 S 1 0,1 q0 0 或：(對(duì), 但稍嫌麻煩) 1 0 1 0 0 1 qt qs q1 S 1 q0 0 q２ 　------------05級(jí)孫磊 錯(cuò)

3、解: 1 0 q0 S q1 q2 1 0 0,1 1 0 q0 S q1 q3 1 0 0,1 q2 0,1 0 (x∈{0,1}*) 1 0 q0 S q1 1 0 (不接受1, 可接受000) (5) {x| x∈{0,1}+且x中含形如10110的子串} 1 1 q0 S q1 q2 q3 q4 q5 0 0 1 1 0 0 0 1 0,1 q0：起始狀態(tài)，以及未讀入1的狀態(tài)； q1：讀入了10110中第1個(gè)符號(hào)(1)的狀態(tài)； q2：讀入了10110中第2個(gè)符號(hào)(0

4、)的狀態(tài)； q3：讀入了10110中第3個(gè)符號(hào)(1)的狀態(tài)； q4：讀入了10110中第4個(gè)符號(hào)(1)的狀態(tài)； q5：讀入了10110中第5個(gè)符號(hào)(0)的狀態(tài)； 易犯的錯(cuò)誤: 狀態(tài)轉(zhuǎn)移時(shí), 不考慮已接受一些字符后所處狀態(tài), 一味地轉(zhuǎn)到開始狀態(tài)，不利用階段性成果，狗熊掰棒子！ 1 1 q0 S q1 q2 q3 q4 q5 0 0 1 1 0 0 0 0,1 1 (7) {x| x∈{0,1}+且把x看成二進(jìn)制數(shù)時(shí)，x模5與3同余，要求中當(dāng)x為0時(shí)，|x|=1，且x≠0時(shí)，x首字符是1} 提示: 和P98例3-5屬同一類型, 這種設(shè)計(jì)如

5、不寫清楚設(shè)計(jì)過(guò)程, 不能服人, 也不能反映你的設(shè)計(jì)方法. 解：按題意，當(dāng)x為0時(shí)，x的長(zhǎng)度為1，即不能出現(xiàn)多于1個(gè)0的全0串；當(dāng)x不為0時(shí)，必須以1開始。又由于0模5與3不同余，故在開始狀態(tài)qs讀入0，則直接進(jìn)入陷阱狀態(tài)qt，即δ(qs,0)= qt。其余狀態(tài)為： q1：對(duì)應(yīng)x模5與1同余的等價(jià)類； q2：對(duì)應(yīng)x模5與2同余的等價(jià)類； q3：對(duì)應(yīng)x模5與3同余的等價(jià)類(終止?fàn)顟B(tài))； q4：對(duì)應(yīng)x模5與4同余的等價(jià)類； q5：對(duì)應(yīng)x模5與0同余的等價(jià)類(x≠0)； 所以，要構(gòu)造的DFA為：M=({qs,q1,q2,q3,q4,q5,qt},{

6、0,1},δ, qs,{ q3}) 狀態(tài)轉(zhuǎn)換函數(shù)δ定義如下： (0)在初始狀態(tài)qs，δ(qs,0)= qt，δ(qs,1)= q1 (1)當(dāng)處于q1狀態(tài)時(shí)，已讀入的x=5n+1, n≥0 由2x+0=5×2n+2，有δ(q1,0)= q2 由2x+1=5×2n+3，有δ(q1,1)= q3 (2)當(dāng)處于q2狀態(tài)時(shí)，已讀入的x=5n+2, n≥0 由2x+0=5×2n+4，有δ(q2,0)= q4 由2x+1=5×(2n+1)+0，有δ(q2,1)= q5 (3)當(dāng)處于q3狀態(tài)時(shí)，已讀入的x=5n+3, n≥0 由2x+0=5

7、×(2n+1)+1，有δ(q3,0)= q1 由2x+1=5×(2n+1)+2，有δ(q3,1)= q2 (4)當(dāng)處于q4狀態(tài)時(shí)，已讀入的x=5n+4, n≥0 由2x+0=5×(2n+1)+3，有δ(q4,0)= q3 由2x+1=5×(2n+2)+4，有δ(q4,1)= q4 (5)當(dāng)處于q5狀態(tài)時(shí)，已讀入的x=5n, n>1 由2x+0=5×2n+0，有δ(q5,0)= q5 由2x+1=5×2n+1，有δ(q5,1)= q1 (6)在陷阱狀態(tài)qt，有δ(qt,0)= qt，δ(qt,1)= qt 1 q2 0 1

8、 qs S q1 q4 q3 0 0 0 1 1 1 1 0 q5 qt 0,1 0 (10) {x| x∈{0,1}+且x中至少含兩個(gè)1 } 0 1 q0 S q1 q2 0 1 0,1 或 0 0 1 S 0 1 0,1 1 ------05級(jí)張士光 錯(cuò)解: 0 1 q0 S q1 q2 0 1 0,1 ------錯(cuò)誤原因? 10、構(gòu)造識(shí)別下列語(yǔ)言的NFA (要求寫出形式化描述) (2) {x| x∈{0,1}+且x中含形如10110的子串} 1 q0 S q1 q

9、2 q3 q4 q5 0,1 0 1 1 0 0,1 錯(cuò)解: 1 q0 S q1 q2 q3 q4 q5 0 1 1 0 0,1 qt 0,1 0 0 0 1 1 -----用的是DFA思維 另一不能算錯(cuò)的錯(cuò)誤: 設(shè)計(jì)DFA 形式化描述時(shí)易犯的錯(cuò)誤: δ(q3,1)= q2 或δ(q3,1)={ q2} (8) {x| x∈{0,1}+且x的首字符和尾字符相同} 1 1 q1 q0 S q2 q3 0,1 0 0 0,1 q4 或 1 1 q1 q0 S q2 q3

10、0,1 0 0 0,1 或(后面的這兩個(gè)解更好!嚴(yán)格講, 前兩解不全對(duì)) 1 1 q1 q0 S q2 q3 0,1 0 0 0,1 q4 0,1 --------05級(jí)孫亮波 或 1 1 q1 q0 S q2 q3 0,1 0 0 0,1 0,1 --------05級(jí)孫磊 11(1)、根據(jù)給定的NFA，構(gòu)造與之等價(jià)的DFA 狀態(tài)說(shuō)明 狀態(tài) 輸入字符 0 1 2 開始狀態(tài) [q0] q0 q1 [q0 q2] [q0 q2] [q0 q1] [q0 q1 q3] [q0 q2] [q0

11、 q2] [q0 q2] [q0 q1] [q0 q1 q2 q3] [q0 q1 q2] 終止?fàn)顟B(tài) [q0 q1 q3] [q0 q1 q2 q3] [q0 q2 q3] [q0 q2] [q0 q1 q2] [q0 q1 q3] [q0 q1 q2 q3] [q0 q1 q2] 終止?fàn)顟B(tài) [q0 q2 q3] [q0 q1 q2 q3] [q0 q1 q2 q3] [q0 q1 q2] 終止?fàn)顟B(tài) [q0 q1 q2 q3] [q0 q1 q2 q3] [q0 q1 q2 q3] [q0 q1 q2] 形式化描述與狀態(tài)轉(zhuǎn)移圖略.

12、不合適的解法: (1)專門列出一個(gè)產(chǎn)生式S?q0 (2)列出2Q中所有狀態(tài)組, 沒有必要; (2)狀態(tài)組不用[ ]括起來(lái), 雖然本質(zhì)上沒有問(wèn)題, 但可能忽略”狀態(tài)集-狀態(tài)組-單個(gè)狀態(tài)”在思維上的轉(zhuǎn)變. 20、構(gòu)造圖3-20所給DFA對(duì)應(yīng)的右線性文法（做左圖） 解： q0?0q1|1q3|1 q1?0q0|1q3|1 q3?0q1|1q1 q2?0q3|1q1|0 補(bǔ)充: 先將無(wú)用狀態(tài)q2去掉再做 ----05級(jí)張志輝, 岳寶提出 不合適的解法: 把非終結(jié)符qi(原自動(dòng)機(jī)中的狀態(tài))換為S,A,B等在文法中常見的符號(hào), 抽象是去除表面的現(xiàn)象, 保留其實(shí)質(zhì)所在, 如果在用的符

13、號(hào)上都得費(fèi)心思變一下才行, 對(duì)抽象能力培養(yǎng)不利(我以這個(gè)理由辯不該換符號(hào), 其實(shí)你也可以同樣的理由辯換了也無(wú)所謂, 但我覺得還是不換為好.) 22(1)、根據(jù)下列所給文法，構(gòu)造相應(yīng)的FA G1：S?a|aA A?a|aA|cA|bB B?a|b|c|aB|bB|cB 解：FA M=({S,A,B,Z}, {a,b,c},d, S, {Z})，其中δ為 d (S,a)= {Z,A} d (A,a)= {Z,A} d (A,c)= { A} d (A,b)= {B} d (B,a)= {Z,B} d (B,b)= {Z,B} d (B,c)= {Z,B} (可以畫出狀態(tài)轉(zhuǎn)移圖) 不合適的解法: 同20題, 換符號(hào) 錯(cuò)誤寫法： 由A?a，δ(A,a)= {Z} 由A?a，δ(A,a)= Z 由A?aA，δ(A,a)= {A} 由A?aA，δ(A,a)= A 應(yīng)該是：由A?a，Z?d(A,a) 由A?aA，A?d(A,a)