形式語言與自動機(jī)課后習(xí)題答案.doc
《形式語言與自動機(jī)課后習(xí)題答案.doc》由會員分享,可在線閱讀,更多相關(guān)《形式語言與自動機(jī)課后習(xí)題答案.doc(9頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
形式語言與自動機(jī)課后作業(yè)答案 第二章 4.找出右線性文法,能構(gòu)成長度為1至5個字符且以字母為首的字符串。 答:G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6.構(gòu)造上下文無關(guān)文法能夠產(chǎn)生 L={ω/ω∈{a,b}*且ω中a的個數(shù)是b的兩倍} 答:G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7.找出由下列各組生成式產(chǎn)生的語言(起始符為S) (1) S→SaS S→b (2) S→aSb S→c (3) S→a S→aE E→aS 答:(1)b(ab)n /n≥0}或者L={(ba)nb /n≥0} (2) L={ancbn /n≥0} (3) L={a2n+1 /n≥0} 第三章 1. 下列集合是否為正則集,若是正則集寫出其正則式。 (1) 含有偶數(shù)個a和奇數(shù)個b的{a,b}*上的字符串集合 (2) 含有相同個數(shù)a和b的字符串集合 (3) 不含子串a(chǎn)ba的{a,b}*上的字符串集合 答:(1)是正則集,自動機(jī)如下 奇a偶b 偶a偶b a a b b b b 奇a奇b 偶a奇b a a (2) 不是正則集,用泵浦引理可以證明,具體見17題(2)。 (3) 是正則集 先看L’為包含子串a(chǎn)ba的{a,b}*上的字符串集合 顯然這是正則集,可以寫出表達(dá)式和畫出自動機(jī)。(略) 則不包含子串a(chǎn)ba的{a,b}*上的字符串集合L是L’的非。 根據(jù)正則集的性質(zhì),L也是正則集。 4.對下列文法的生成式,找出其正則式 (1) G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下: S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d (2) G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下: S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答:(1) 由生成式得: S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化簡消去CD,得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 將②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得: S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 將⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 將⑥⑦代入② A=b+a+c(d+b+a) ⑧ 將⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.為下列正則集,構(gòu)造右線性文法: (1){a,b}* (2)以abb結(jié)尾的由a和b組成的所有字符串的集合 (3)以b為首后跟若干個a的字符串的集合 (4) 含有兩個相繼a和兩個相繼b的由a和b組成的所有字符串集合 答:(1)右線性文法G=({S},{a,b},P,S) P: S→aS S→bS S→ε (2) 右線性文法G=({S},{a,b},P,S) P: S→aS S→bS S→abb (3) 此正則集為{ba*} 右線性文法G=({S,A},{a,b},P,S) P: S→bA A→aA A→ε (4) 此正則集為{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*} 右線性文法G=({S,A,B,C},{a,b},P,S) P: S→aS/bS/aaA/bbB A→aA/bA/bbC B→aB/bB/aaC C→aC/bC/ε 7.設(shè)正則集為a(ba)* (1) 構(gòu)造右線性文法 (2) 找出(1)中文法的有限自動機(jī) 答:(1)右線性文法G=({S,A},{a,b},P,S) P: S→aA A→bS A→ε (2)自動機(jī)如下: P2 P1 a b (p2是終結(jié)狀態(tài)) 9.對應(yīng)圖(a)(b)的狀態(tài)轉(zhuǎn)換圖寫出正則式。(圖略) (1) 由圖可知q0=aq0+bq1+a+ε q1=aq2+bq1 q0=aq0+bq1+a =>q1=abq1+bq1+aaq0+aa =(b+ab) q1+aaq0+aa =(b+ab) *( aaq0+aa) =>q0=aq0+b(b+ab) *( aaq0+aa ) +a+ε = q0(a+b (b+ab) *aa)+ b(b+ab) *aa+a+ε =(a+b (b+ab) *aa) *((b+ab) *aa+a+ε) =(a+b (b+ab) *aa) * (3) q0=aq1+bq2+a+b q1=aq0+bq2+b q0=aq1+bq0+a =>q1=aq0+baq1+bbq0+ba+b =(ba)*(aq0 +bbq0+ba+b) =>q2=aaq0+abq2+bq0+ab+a =(ab)*(aaq0 +bq0+ ab+a) =>q0=a(ba)*(a+bb) q0 + a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab+a)+a+b =[a(ba)*(a+bb) +b(ab)*(aa+b)]* (a(ba)*(ba+b)+ b(ab)*(ab+a)+a+b) 10.設(shè)字母表T={a,b},找出接受下列語言的DFA: (1) 含有3個連續(xù)b的所有字符串集合 (2) 以aa為首的所有字符串集合 (3) 以aa結(jié)尾的所有字符串集合 答:(1)M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下: a b q0 q0 q1 q1 q0 q2 q2 q0 q3 q3 q3 q3 (2)M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下: a b q0 q1 Φ q1 q2 Φ q2 q2 q2 (3)M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下: a b q0 q1 q0 q1 q2 q0 q2 q2 q0 14構(gòu)造DFA M1等價于NFA M,NFA M如下: (1)M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下: σ(q0,a)={q0,q1} σ(q0,b)={q0} σ(q1,a)={q2} σ(q1,b)= {q2 } σ(q2,a)={q3} σ(q2,b)= Φ σ(q3,a)={q3} σ(q3,b)= {q3 } (2)M=({q0,q1 q2,q3},{a,b},σ,q0,{ q1,q2}),其中σ如下: σ(q0,a)={q1,q2} σ(q0,b)={q1} σ(q1,a)={q2} σ(q1,b)= {q1,q2 } σ(q2,a)={q3} σ(q2,b)= {q0} σ(q3,a)= Φσ(q3,b)= {q0} 答:(1)DFA M1={Q1, {a,b},σ1, [q0],{ [q0,q1,q3],[q0,q2,q3],[q0, q1,q2,q3]} 其中Q1 ={[q0],[q0,q1], [q0,q1,q2],[ q0,q2],[ q0,q1, q2,q3],[ q0,q1, q3],[ q0,q2, q3],[ q0,q3]} σ1滿足 a b [q0] [q0,q1] [ q0] [q0,q1] [q0,q1,q2] [ q0,q2] [q0,q1,q2] [ q0,q1, q2,q3] [ q0,q2] [ q0,q2] [ q0,q1, q3] [q0] [ q0,q1, q2,q3] [ q0,q1, q2,q3] [ q0,q2, q3] [ q0,q1, q3] [ q0,q1, q2,q3] [ q0,q2, q3] [ q0,q2, q3] [ q0,q1, q3] [ q0,q3] [ q0,q3] [ q0,q1, q3] [ q0,q3] (2)DFA M1={Q1, {a,b},σ1, [q0],{ [q1],[q3], [q1,q3],[q0,q1,q2],[q1,q2] ,[q1,q2,q3],[q2,q3]} 其中Q1 ={[q0],[q1,q3], [q1],[q2],[ q0,q1,q2],[q1,q2],[q3], [q1,q2,q3],[q2,q3]} σ1滿足 a b [q0] [q1,q3] [q1] [q1,q3] [q2] [ q0,q1,q2] [q1] [q2] [q1,q2] [q2] [q3] [q0] [ q0,q1,q2] [q1,q2,q3] [ q0,q1,q2] [q1,q2] [q2,q3] [ q0,q1,q2] [q3] Φ [q0] [q1,q2,q3] [q2,q3] [ q0,q1,q2] [q2,q3] [q3] [q0] 15. 15.對下面矩陣表示的ε-NFA ε a b c P(起始狀態(tài)) φ {p} {q} {r} q {p} {q} {r} φ r(終止?fàn)顟B(tài)) {q} {r} φ {p} (1) 給出該自動機(jī)接收的所有長度為3的串 (2) 將此ε-NFA轉(zhuǎn)換為沒有ε的NFA 答:(1)可被接受的的串共 23個,分別為aac, abc, acc, bac, bbc, bcc, cac, cbc, ccc, caa, cab, cba, cbb, cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb (2)ε-NFA:M=({p,q,r},{a,b,c},σ,p,r) 其中σ如表格所示。 因?yàn)棣?closure(p)= Φ 則設(shè)不含ε的NFA M1=({p,q,r},{a,b,c},σ1,p,r) σ1(p,a)=σ’(p,a)=ε-closure(σ(σ’(p,ε),a))={p} σ1(p,b)=σ’(p,b)=ε-closure(σ(σ’(p,ε),b))={p,q} σ1(p,c)=σ’(p,c)=ε-closure(σ(σ’(p,ε),c))={p,q,r} σ1(q,a)=σ’(q,a)=ε-closure(σ(σ’(q,ε),a))={p,q} σ1(q,b)=σ’(q,b)=ε-closure(σ(σ’(q,ε),b))={p,q,r} σ1(q,c)=σ’(q,c)=ε-closure(σ(σ’(q,ε),c))={p,q,r} σ1(r,a)=σ’(r,a)=ε-closure(σ(σ’(r,ε),a))={p,q,r} σ1(r,b)=σ’(r,b)=ε-closure(σ(σ’(r,ε),b))={p,q,r} σ1(r,c)=σ’(r,c)=ε-closure(σ(σ’(r,ε),c))={p,q,r} 圖示如下:(r為終止?fàn)顟B(tài)) p q b,c a,b,c a,b,c a,b,c c a,b,c b,c a,b,c r a,b,c 16.設(shè)NFA M=({q0,q1},{a,b},σ,q0,{q1}),其中σ如下: σ(q0,a)={q0,q1} σ(q0,b)={q1} σ(q1,a)= Φ σ(q1,b)= {q0, q1} 構(gòu)造相應(yīng)的DFA M1,并進(jìn)行化簡 答:構(gòu)造一個相應(yīng)的DFA M1={Q1, {a,b},σ1, [q0],{ [q1],[q0,q1]} 其中Q1 ={[q0],[q1],[q0,q1]} σ1滿足 a b [q0] [q0,q1] [q1] [q1] Φ [q0,q1] [q0,q1] [q0,q1] [q0,q1] 由于該DFA已是最簡,故不用化簡 17.使用泵浦引理,證明下列集合不是正則集: (1) 由文法G的生成式S→aSbS/c產(chǎn)生的語言L(G) (2) {ω/ω∈{a,b}*且ω有相同個數(shù)的a和b} (3) {akcak/k≥1} (4) {ωω/ω∈{a,b}*} 證明:(1)在L(G)中,a的個數(shù)與b的個數(shù)相等 假設(shè)L(G)是正則集,對于足夠大的k取ω= ak (cb)kc 令ω=ω1ω0ω2 因?yàn)閨ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以對于任意ω0只能取ω0=an n∈(0,k) 則ω1ω0iω2= ak–n(an)i(cb)kc 在i不等于0時不屬于L 與假設(shè)矛盾。則L(G)不是正則集 (2)假設(shè)該集合是正則集,對于足夠大的k取ω= ak bk 令ω=ω1ω0ω2 因?yàn)閨ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以對于任意ω0只能取ω0=an n∈(0,k) 則ω1ω0iω2= ak–n(an)ibk 在i不等于0時a與b的個數(shù)不同,不屬于該集合 與假設(shè)矛盾。則該集合不是正則集 (3)假設(shè)該集合是正則集,對于足夠大的k取ω= ak cak 令ω=ω1ω0ω2 因?yàn)閨ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以對于任意ω0只能取ω0=an n∈(0,k) 則ω1ω0iω2= ak–n(an)icak 在i不等于0時c前后a的個數(shù)不同,不屬于該集合 與假設(shè)矛盾。則該集合不是正則集 (4)假設(shè)該集合是正則集,對于足夠大的k取ωω= ak bakb 令ωω=ω1ω0ω2 因?yàn)閨ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以對于任意ω0只能取ω0=an n∈(0,k) 則ω1ω0iω2= ak–n(an)ibakb 在i不等于0時不滿足ωω的形式,不屬于該集合 與假設(shè)矛盾。則該集合不是正則集 18.構(gòu)造米蘭機(jī)和摩爾機(jī) 對于{a,b}*的字符串,如果輸入以bab結(jié)尾,則輸出1;如果輸入以bba結(jié)尾,則輸出2;否則輸出3。 答:米蘭機(jī): 說明狀態(tài)qaa表示到這個狀態(tài)時,輸入的字符串是以aa結(jié)尾。其他同理。 a/3 qaa qab b/3 a/3 a/3 b/3 b/1 qba qbb a/2 b/3 摩爾機(jī),狀態(tài)說明同米蘭機(jī)。 a a qaba,3 b/3 qaab,3 b/3 qaa,3 b/3 b a a b a b qbab,1 b/3 qbb,3 b/3 qbba,2 b/3 a b b b- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 形式語言 自動機(jī) 課后 習(xí)題 答案
鏈接地址:http://m.appdesigncorp.com/p-6573548.html