《《形式語言與自動機》王柏、楊娟編著課后習題答案》由會員分享，可在線閱讀，更多相關(guān)《《形式語言與自動機》王柏、楊娟編著課后習題答案（15頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、形式語言與自動機課后習題答案 第二章 4.找出右線性文法，能構(gòu)成長度為1至5個字符且以字母為首的字符串。 答：G={N,T,P,S} P如下: 其中N={S,A,B,C,D} T={x,y} 其中x C {所有字母} y C {所有的字符} 5— x S-xA A - y A - yB B-y B-yC C - y C-yDD-y 6 .構(gòu)造上下文無關(guān)文法能夠產(chǎn)生 L={ 3 / 3 C {a,b}*且3中a的個數(shù)是b的兩倍} 答：G={N,T,P,S} 其中 N={S} T={a,b} P 如下： 5— aab S-^ aba S—baa 6— aabS S—aaS

2、b S— aSab S-Saab 7— abaS S—abSa S— aSba S-Saba 8— baaS S—baSa S— bSaa S-Sbaa 7 .找出由下列各組生成式產(chǎn)生的語言(起始符為S) ⑴ 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={a ncbn /n > 0} (3) L={a 2n+1 /n >0} 第三章 1.下列集合是否為正則集，若是正則集寫出其正則式。 (1) 含有偶數(shù)個a和奇數(shù)個b的{a,b}*

3、上的字符串集合 (2) 含有相同個數(shù)a和b的字符串集合 (3) 不含子串a(chǎn)ba的{a,b}*上的字符串集合 答：(1)是正則集，自動機如下 (2)不是正則集，用泵浦引理可以證明，具體見 17題(2) (3)是正則集 先看L'為包含子串a(chǎn)ba的{a,b}*上的字符串集合 顯然這是正則集，可以寫出表達式和畫出自動機。(略) 則不包含子串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 —

4、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+ e )(c

5、b) *(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)造右線性文法： ⑴{a,b}* ⑵以abb結(jié)尾白^由a和b組成的所有字符串的集合 (3)以b為首后跟若干個a的字符串的集合 (4)含有兩個相繼a和兩個相繼b的由a和b組成的所有字符串集合 答：(1)右線性文法 G=(

6、{S},{a,b},P,S) P: S— aS SH> bS S— e (2)右線性文法 G=({S},{a,b},P,S) P: S— aS S-^ bS S— abb (3)此正則集為{ba*} 右線性文法 G=({S,A},{a,b},P,S) P: Sf bAA - aA A-e (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

7、.設(shè)正則集為a(ba)* (1)構(gòu)造右線性文法 (2)找出(1)中文法的有限自b動機 答：(1)右線性文法 G=({S,A},{a,b},P,S) P: Sf aA A -bS A 一 e (2)自動機如下： ； =^22^ (p2是終結(jié)狀態(tài)) 9.對應(yīng)圖(a) (b)的狀態(tài)轉(zhuǎn)換圖寫出正則式。(圖略) (1) 由圖可知 qo=aq o+bq 1+a+ ￡ q〔=aq2+bq1 qo=aqo+bq1+a =>q1=abq1+bq1+aaq o+aa =(b+ab) q 1+aaqo+aa =(b+ab) *( aaq o+aa) =>q o=aq o+b(b+ab)

8、 *( aaq o+aa ) +a+ & =q o(a+b (b+ab) *aa)+ b(b+ab) *aa+a+ e =(a+b (b+ab) *aa) *((b+ab) *aa+a+ e ) =(a+b (b+ab) *aa) * (3) qo=aq 1+bq2+a+b q1=aqo+bq2+b qo=aq1+bq o+a =>q 1=aq o+baq 1+bbq o+ba+b =(ba)*(aq o +bbq o+ba+b) =>q 2=aaqo+abq2+bq o+ab+a =(ab)*(aaq o +bq o+ ab+a) =>q o=a(ba)*(a+bb)

9、q 0 + a(ba)*(ba+b)+b(ab)*(aa+b)q 0+ 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=({q o,qi q2,q3},{a,b},(T ,qo,{q3}),其中 b如下： a b q0 q0 q1 q1 q0 q2 q2 q0 q3

10、 q3 q3 q3 ⑵ M=({q o,qi q2 },{a,b}, b ,qo,{q2}),其中 o?如下: a b q0 q1 ① q1 q2 ① q2 q2 q2 (3) M=({q 0,q1 q2 },{a,b}, v ,q0,{q2}),其中 b如下: a b q0 q1 q0 q1 q2 q0 q2 q2 q0 14構(gòu)造DFA Mi等價于NFA M, NFA M如下： (1) M=({q o,q1 q2,q3},{a,b},(T ,qo,{q3}),其中 b如下： 6 (qo,a戶{qo,q1} g (

11、qo,b)={q 0} (T (q1,a)={q 2} b(q1,b戶{q 2 } d (q2,a)={q 3}b (q2,b戶 中 d (q3,a)={q 3} b (q3,b戶{q 3 } (2) M=({q 0,q1 q2,q3},{a,b},(T ,q0,{q1,q2}),其中 o?如下: 6 (q0,a)={q1,q2}g (q0,b)={q 1} d (q1,a)={q 2}(r(q1,b尸{q 1,q2 } (T (q2,a)={q 3}b (q2,b戶{q 0} (r(q3,a尸 ①(r(q3,b戶{q。} 答：(1) DFA M 尸{Q1, {a,b},門，

12、[q0],{ [q0,q1,q3], [q0,q2,q3], [q0, q1,q2,q3]} 其中 Q1 ={[q 0],[q0,q1], [q0,q1,q2],[ q0,q2],[ q 0,q[，q2,q3],[ q0,q1, q3],[ q0,q2, q3],[ q 0,q3]} b 1滿足 a b [q0] [q0,q1] [q0] [q 0,q1] [q 0,q1,q2] [q0,q2] [q0,q1,q2] [q0,q1, q2,q3] [q0,q2] [q0,q2] [q0,q1, q3] [q 0] [q0,q1, q2,q3] [q0,

13、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] ⑵ DFA M i={Q i, {a,b},(T i, [qo],{ [q i],[q 3], [q i,q3],[q o,qi,q2],[qi,q2] ,[q 1 ,q2,q3],[q 2,q3]} 其中 Q1 ={[q 0],[q 1,q3], [q 1],[q 2],[ q 0,q1,q2],[q 1,q2],[q 3

14、], [q 1,q2,q3],[q 2,q3]} 0-1滿足 a b [q0] [q1,q3] 一[q1] [q1,q3] [q 2] [q0,q1,q2] [q1] [q2] [q1,q2] [q2] [q3] r[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

15、 b c p（起始狀態(tài)） {p} ]{q} {r} q {p} {q} {r} r（終止狀態(tài)） {q} {r} {p} (1)給出該自動機接收的所有長度為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}, b ,p

16、,r)其中。如表格所示。 因為e -closure(p戶① 則設(shè)不含 e 的 NFA M=({p,q,r},{a,b,c},(r1,p,r) (T1(p,a尸(T'(p,a尸 e -closure( o- ((T'(p, e ),a))={p} (n(p,b)= o- '(p,b尸 e -closure( o- ( o- '(p, e ),b))={p,q} o-1(p,c)= o- \p,c)= e -closure( o- ( o- \p, e ),c))={p,q,r} o-1(q,a)= o- '(q,a尸 e -closure( o- ( o- '(q, e ),a))=

17、{p,q} (n(q,b)= o- '(q,b尸 e -closure( o- ( o- '(q, e ),b))={p,q,r} o-1(q,c)= o- '(q,c尸 e -closure( (r( o- '(q, e ),c))={p,q,r} o-1(r,a)= o- '(r,a尸 e -closure( o- ( o- '(r,e ),a))={p,q,r} (n(r,b)= o- \r,b)= e -closure( o- ( o*'(r,e ),b))={p,q,r} o-1(r,c)= o- '(r,c尸 e -closure( o- ( o- '(r, e ),c)

18、)={p,q,r} 圖示如下：（r為終止狀態(tài)） b,c a,b,c a,b,c a,b,c 16.設(shè) NFA M=({q 0,qi},{a,b},』,q0,{qi}),其中一如下: 6 (qo,a戶{qo,qi}g (qo,b)={q 1} (r(q1,a尸 中(r(q1,b)= {q 0, q1} 構(gòu)造相應(yīng)的DFA Mi,并進行化簡 答：構(gòu)造一個相應(yīng)的DFA M i={Q 1, {a,b},(T 1, [q0],{ [q i], [q 0,qi]} 其中 Q1 ={[q。], [q[], [q0,q1]} b 1滿足 a b [q0] [q0,q1

19、] [q1] [q1] ① [q 0,q1] [q 0,q1] [q0,q1] [q 0,q1] 由于該DFA已是最簡，故不用化簡 17 .使用泵浦引理，證明下列集合不是正則集： (1) 由文法G的生成式S-aSbS/c產(chǎn)生的語言L(G) (2) {3/3 C {a,b}*且3有相同個數(shù)的 a和b} (3) {akcak/k > 1} (4) { 3 3 / 3 C {a,b}*} 證明：(1)在L(G)中，a的個數(shù)與b的個數(shù)相等 假設(shè)L(G)是正則集，對于足夠大的k取3=a k (cb) kc 令==313032 因為 | 3 0|>0 |3 1 3 o

20、| < k 存在 3 0使 3 1 3 0i 3 2 C L 所以對于任意3 o只能取3 o=an n C (0,k) 則3130i32= ak n(an)i(cb) kc在i不等于0時不屬于L 與假設(shè)矛盾。則L(G)不是正則集 (2)假設(shè)該集合是正則集，對于足夠大的k取3=ak bk 令 = =313032 因為 | 3 0|>0 | 3 1 3 0| < k 存在 3 0使 3 1 CO 0 3 2 C L 所以對于任意3 0只能取3 0=an n C (0,k) 則3130i32= ak n(an)ibk在i不等于0時a與b的個數(shù)不同，不屬于該集合 與假設(shè)矛盾。則該集合

21、不是正則集 (3)假設(shè)該集合是正則集，對于足夠大的k取3=ak cak 令3 = 313032 因為 | 3 0|>0 |3 1 3 0| < k 存在 00 0使 3 1 3 0i 3 2 C L 所以對于任意3 0只能取3 o=an n C (0,k) 則3i30i32=ak-n(an)icak在i不等于0時c前后a的個數(shù)不同，不屬于該集合 與假設(shè)矛盾。則該集合不是正則集 (4)假設(shè)該集合是正則集，對于足夠大的k取3①=ak bakb 令3 3 =313032 因為 | 3 0|>0 |3 1 3 0| < k 存在 3 0使 3 1 3 0i 3 2 C L 所以對于任

22、意3 0只能取3 0=an n C (0,k) 則3 13 0i 3 2= ak n(an)ibakb 在i不等于0時不滿足①①的形式，不屬于該集合 與假設(shè)矛盾。則該集合不是正則集 18 .構(gòu)造米蘭機和摩爾機 對于{a,b}*的字符串，如果輸入以bab結(jié)尾，則輸出1;如果輸入以bba結(jié)尾，則輸 出2；否則輸出3。 答：米蘭機： 說明1犬態(tài)qaa表示到這個狀態(tài)時，輸入的字符串是以aa結(jié)尾。其他同理。 b/3 摩爾機，狀態(tài)說明同米蘭機 aba b b ?第四章 10 .把下列文法變換為無￡生成式、無單生成式和沒有無用符號的等價文法: S 一A1 |

23、A 2 , A1 一A3 | A 4 , A2 一A4 | A 5 , A3 一S | b | d | & 解：⑴ 由算法3,變換為無￡生成式： N ’ = { S, A1,A2,A3,A4,A5 } G1 = ( { S1,S, A1,A2A3,A4,A5 } , { a,b,d }, P 1 , Si )，其中生成式 Pi如下: Si f ￡ | S , S -Ai | A 2 , Ai —A3|A 4, A2 -A4|A 5 , A3 —S | b , A4 — S | a , A5 —S|d , ⑵ 由算法4，消單生成式： Ns1 = { Si,S,Ai,A2,A3,A4,

24、 A5 } , N S = N Ai = N A2 = N A3 = N A4 = N A5 = { S, A i,A 2,A3,A4, A 5 } , 運用算法4，則Pi 變?yōu)椋? Si —a | b | d |& S —a | b | d , Ai —a A2 —a A3 —a A4 —a b b b b b d , d , d , d , d ⑶ 由算法 i 和算法 2，消除無用符號，得到符合題目要求的等價文法： 得到符合題目要求的等價文法: A5 —a Gi = ( { Si } , { a,b,d } , Pi , Si ),其中生成式 Pi 為：Si -a

25、 | b | d |￡ . 11 . 設(shè) 2 型文法 G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中 P： S —ASB | ￡ ; A —aAS | a ; B —SBS | A | bb 試將G變換為無￡生成式，無單生成式，沒有無用符號的文法，再將其轉(zhuǎn)換為 Chomsky 范式 . 解：⑴ 由算法3,變換為無￡生成式： N’ = { S } 由 S —ASB 得出 S — ASB | AB , 由 A —aAS 得出 A —aAS | aA , 由 B —SBS得出 B —SBS | SB | BS |B, 由 SC

26、N'得出 Si f e | S , 因此無￡的等效文法 Gi = ( { Si,S,A,B } , { a,b,d } , P i , Si )，其中生成式Pi如下: Si f ￡ | S , S — ASB | AB , A —aAS | aA | a, B —SBS | SB | BS | B| A | bb , ⑵ 由算法4，消單生成式： NSi = { Si,S } , NS = { S } , NA = { A } , NB = { A,B } 由于S -ASB | AB C P且不是單生成式，故Pi中有Si f e | ASB | AB , 同理有 S — ASB

27、| AB , A —aAS | aA | a , B —SBS | SB | BS | aAS | aA | a | bb, 因此生成的無單生成式等效文法為 Gi = ( { Si,S, A,B } , { a,b } , Pi , Si )，其中生成式 Pi 如下： Si — e | ASB | AB , S —ASB | AB , A —aAS | aA | a , B —SBS | SB | BS | aAS | aA | a | bb, ⑶ 由算法 i 和算法2，消除無用符號(此題沒有無用符號); ⑷ 轉(zhuǎn)化為等價的 Chomsky 范式的文法: 將 Si —ASB 變

28、換為 S —AC, C —SB , 將S —ASB變換為S —AC , 將 A —aAS | aA 變換為 A — ED | EA, D —AS , E —a, 將 B —SBS | aAS | aA | a | bb , 變換為 B —CS | ED | EA | FF, F—b , ⑸ 由此得出符合題目要求的等價文法： Gi = ( { Si,S, A,B,C,D } , { a,b } , P i , Si )，其中生成式 Pi 如下： Si — e | AC | AB , S —AC | AB , A —ED | EA | a , B —CS | SB | BS |

29、ED | EA | a | FF , C —SB , D —AS , E —a , F —b . 15. 將下列文法變換為等價的 Greibach 范式文法 : (1) S —DD | a , D —SS | b 解 : 將非終結(jié)符排序為 S,D,S 為低位 ,D 為高位 , ⑴ 對于D —SS用S —DD | a 代入得 D — DDS | aS | b , 用引理 4.2.4,變化為 D —aS | b | aSD' | bD' , D ' —DS | DSD ', ⑵ 將D生成式代入 S生成式得 S — aSD | bD | aSD 'D | bD'D | a ,

30、⑶ 將 D 生成式代入 D ’生成式得 D' — aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D', ⑷ 由此得出等價的 Greibach 范式文法： Gi = ( { S,D,D' } , { a,b } , Pi , S )，其中生成式 Pi如下： S —aSD | bD | aSD D | bD'D | a , D —aS | b | aSD' | bD', D' —aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D'. ⑵ Ai

31、—A3b | A 2a , A2 —Aib | A 2A2a | b , A 3 —Aia | A 3A3b | a 解 : ⑴ 轉(zhuǎn)化為等價的 Chomsky 范式的文法: Ai —A3A4 | A 2A5 , A2 - AiA4 | A 2A6 | b , A3 - AiA5 | A 3A7 | a , A4 — b , A5 —a , A6 —A 2A 5 , A 7 —A 3A 4 , ⑵ 轉(zhuǎn)化為等價的 Greibach 范式的文法: 將非終結(jié)符排序為 Al, A 2A3A 4A 5,A1為低位A 5為高位, ①對于 A2 — A1A4，用 A1 —A 3A4 |

32、A2A 5代入得 A2 —A 3A4A4 | A2 A5A4 | A2A6 | b , 用引理4.2.4,變化為 A2 -A3A4A4 | b | A 3A4A4A2'| bA 2', A2' fA5A4A2' | A 6A2' | A 5A4 | A 6 , ②對于 A3 —A1A5，用 Ai —A3A4 | A2A5代入得 A3 fA3A4A5 | A2A5A5 | A 3A 7 | a , A 3生成式右邊第一個字符仍是較低位的非終結(jié)符，將A2生成式代入A 3生成式 得 A3 - A3A4 A5 | A 3A4A4 A5A5 | b A 5A5 | A 3A4A4A2' A

33、5A5 | bA 2'A5A5 | A 3A7 | a , 用引理4.2.4,變化為 A3 —b A5A5 | bA 2'A5A5 | a | b A 5A5A3'| bA 2'A5A5A3'| aA 3’, A3' fA4A5 | A4A4A5A5 | A4A4A2'A5A5 | A7 | A4A5A3' | A4A4A5A5A3' | A4A4A2’A5A5A 3’ | A 7A3’ , ③對于A 6 fA 2A 5，將A2生成式代入A 6生成式得 A6 -A3A4A4A5 | bA 5 | A 3A4A4A2'A5 | bA 2^5 , A6生成式右邊第一個字符仍是較低位的非

34、終結(jié)符，將A3生成式代入A6生成式 得 A6 -bA 5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA 5A5A3'A4A4A5 | bA2’A5A5A3’A4A4A5 | aA 3’A4A4A5 | bA 5A5A4A4A2’A5 | bA 2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA 5A5A3’A4A4A2’A5 | bA 2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA 2’A5 | b A 5 , ④對于A7 fA3A4 ,將A3生成式代入 A7生成式得 A7 -b A5A5A4 | bA2'

35、A5A5A4 | a A4 1b A5A5A3'A4 | bA2'A5A5A3A4 | aA3’A4 , ⑤將A5,A6生成式代入A2,生成式得 A2’ — aA4A2' | bA 5A5A4A4A5A2' | bA 2'A5A5A4A4A5A2' | aA4A4A5A2' | bA 5A5A3’A4A4A5A2’ |bA 2’A5A5A3’A4A4A5A2’|aA3’A4A4A5A2’ | bA 5A5A4A4A2’A5 A2’ |bA 2’A5A5A4A4A2’A5A2’ |aA4A4A2’A5A2’ | bA 5A 5A 3’A 4A 4A 2’A 5A 2 ’ | bA 2’A

36、 5A 5A 3’A 4A 4A 2’A 5A 2 ’ | aA3’A 4A 4A 2’A 5A 2’ | bA2’A5A2’ | b A 5A2’ | aA 4 | b A 5A5A4A4A5 | bA 2’A5A5A4A4A5 | aA 4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA 2’A5A5A4A4A2’A5| aA4A4A2’A5| bA 5A5A3’A4A4A2’A5| bA2’A5A5A3’A4A4A2’A5 | aA 3’A4A4A2’A5 | bA 2’A5 | b

37、 A 5 , 將A4,A7生成式代入A3,生成式得 A3' — aA5 | aA 4A5A5 | aA 4A2A5A5 | aA 5A3'| aA 4A5A5A3'| aA 4A2'A5A5A3' | b A 5A5A4 | bA 2’A5A5A4 | aA 4 | bA 5A5A3’A4 | bA 2’A5A5A3’A4 | aA 3’A4 | bA5A5A4A3’ | bA 2’A5A5A4A3’ |a A4A3’ | b A 5A5A3’A4 A 3’ | bA 2’A5A5A3’A4 A3’ | aA 3’A4A3’ , ⑶ 由此得出等價的 Greibach 范式文法 : Gi

38、= ( { S,D,D' } , { a,b } , Pi , S )，其中生成式 Pi如下： Ai —A3A4 | A 2A5 , A2 -A3A4A4 | b | A 3A4A4A2'| bA 2‘， A3 -b A5A5 | bA 2'A5A5 | a | bA 5A5A3’| bA 2^663] aA 3', A4 — b , A5 —a , A6 -bA 5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA 5A5A3'A4A4A5 | bA2’A5A5A3’A4A4A5 | aA 3’A4A4A5 | bA 5A5A4A4A2’A5 | bA

39、 2’A5A5A4A4A2’A5 | aA4A4A2 ’A5 | bA 5A5A3’A4A4A2’A5 | bA 2’A5A5A3’A4A4A2 ’A5 | aA3’A4A4A2’A5 | bA 2’A5 | b A 5 , A7 -b A5A5A4 | bA2'A5A5A4 | a A4 1b A5A5A3'A4 | bA2'A5A5A3A4 | aA3’A4 , A2' f aA4A2' | bA 5A5A4A4A5A2' | bA2'A5A5A4A4A5A2' | aA4A4A5A2' | bA 5A5A3’A4A4A5A2’ | bA 2’A5A5A3’A4A4A5A2’ | aA

40、3’A4A4A5A2’ | bA 5A5A4A4A2’A5 A2’ | bA 2’A5A5A4A4A2’A5A2’ | aA4A4A2’A5A2’ | bA 5A 5A 3’A4A4A2’A5A2 ’ | bA 2’A5A5A 3’A4A4A2’A5A2 ’ | aA3’A4A4A2’A5A2’ | bA2’A5A2’ | bA 5A2’ | aA 4 | b A 5A5A4A4A5 | bA 2’A5A5A4A4A5 | aA 4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5

41、A4A4A2’A5 |aA4A4A2’A5 |bA 5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA 3’A4A4A2’A5 | bA 2’A5 | b A 5 , A3' — aA5 | aA 4A5A5 | aA 4A2A5A5 | aA 5A3' | aA 4A5A5A3' | aA 4A2'A5A5A3' | b A 5A5A4 | bA 2’A5A5A4 | aA 4 | bA 5A5A3’A4 | bA 2’A5A5A3’A4 | aA 3’A4 | bA5A5A4A3’ | bA 2’A5A5A4A3’ |a A4 A3’ | b A 5

42、A5A3’A4 A3’ | bA 2’A5A5A3’A4 A3’ | aA 3’A4A3’ . 20 .設(shè)文法G有如下得生成式：S -aDD, D -aS | bS | a ,構(gòu)造等價的下推自動機. 解: 根據(jù)Pi62-i63 的算法,構(gòu)造下推自動機M, 使 M 按文法 G 的最左推導方式工作. 設(shè) M = (Q,T, T, B ,qo,Zo,F ),其中 Q = { q 0,qf } , T = { a,b} , r = { a,b,D,S }, Zo = S , F = { qf } , B定義如下： B( qo, ￡ ,S) = { ( qo, aDD ) }, B

43、 (q0, ￡,D ) = { ( q 0,aS ) ,( q0,bS) , ( q0,a)}, B (q0,a,a ) = { ( q0, ￡ ) }, B (qo, e, e ) = { ( q f, e )}. 21 .給出產(chǎn)生語言L = { a ibjck | i , j ,k>o且i= j或者j = k}的上下文無關(guān)文法.你給 出的文法是否具有二義性?為什么? 解 : G=({S,A,B,C,D,E},{a,b,c} ， P， S) P: S —AD |EB, A —aAb | ￡ , B —bBc | ￡ , D —cD | ￡ , E —aE | & 文法具有二義性

44、。 因為當句子3中a,b,c個數(shù)相同時，對于3存在兩個不同的最左（右）推導。 如 abc L ， 存 在 兩 個 不 同 的 最 左 推 導 S AD aAbD abD abcC abc 及 S EB aEB aB abBc abc 。 22 .設(shè)下推自動機 M = ( {q o,qi},{a,b},{Z o,X}, B , qo, Z0, 6 ),其中 B 如下： B (q0,b, Z0) = {(q0, XZ0)} , B (q0, e , Z0) = {(q 0, ￡ )} ,A B(qo,b, X) = {(q 0, XX)} , B(qi,b, X) = {(q 1, ￡

45、 )}, B (q0,b, X) = {(q 1, X)} , B (qi,a, Z0) = {(q 0, Z0)}, 試構(gòu)造文法G 產(chǎn)生的語言 L (G) = L(M). 解: 在 G 中 ,N = { [q 0,Z0,q0], [q0,Z0,q1], [q0,X,q0], [q 0,X,q1], [q 1,Z0,q0], [q 1,Z0,q1], [q 1,X,q 0], [q1,X,q1] } . ⑴ S 生成式有 S — [q0,Z0,q0], S - [q0,Z0,qi], 根據(jù) B (q0,b, Z0) = {(q 0, XZ0)}，則有 [q0,Z0,q0] — b[

46、q0,X,q0] [q0,Z0,q0], [q0,Z0,q0] — b[q0,X,qi] [q i,Z0,q0], [q0,Z0,qi] — b[q0,X,q0] [q0,Z0,qi], [q0,Z0,q1] — b[q0,X,q1] [q 1,Z0,q1], 因為有 B (q0,b, X) = {(q 0, XX)},則有 [q0,X,q0] — b[q0,X,q0] [q0,X,q0], [q0, X,q0] — b[q0,X,qi] [qi, X,q0], [q0, X,q1] — b[q0,X,q0] [q0, X,q1], [q0, X,qi] - b[q0,X,qi

47、] [qi, X,qi], 因為有 B (q0,a, X) = {(q 1, X)},則有 [q0,X,q0] -^a[qi,X,q0], [q0,X,qi] -^a[qi,X,qi], 因為有 B (qi,a, Z0) = {(q 0, Z0)},則有 [qi,Z0,q0] —a[q0,Z0,q0], [qi,Z0,qi] -^a[q0,Z0,qi], 因為有 B (q0, ￡ , Z0) = {(q 0, e)},則有 [q0,Z0,q0] — & , 因為有 B (qi,b, X) = {(q i, e )},則有 [qi,X,qi] — e ⑵ 利用算法i和算法2,

48、消除無用符號后，得出文法G產(chǎn)生的語言L(G) = { N,T,P,S } 其中 N = { S,[q 0,Z0,q0],[q i,Z0,q0],[q i,X,qi], [q 0,X,qi] },T = { a,b }, 生成式 P 如下 : S — [q0,Z0,q0], [q0,Z0,q0] — b[q0,X,qi] [q i,Z0,q0], [q0, X,q1] -^b[q 0,X,q i] [q i, X,q1], [q0,X,qi] -^a[qi,X,qi], [qi,Z0,q0] —a[q0,Z0,q0], [q0,Z0,q0] — & , [q0,Z0,q0] — e

49、 . 23 . 證明下列語言不是上下文無關(guān)語言: (1) { anbncm | m < n }; 證明： 假設(shè)L是上下文無關(guān)語言，由泵浦引理，取常數(shù)p,當3cL且131Ap時，可取 3 = aPbPCP，將3 寫為 3 =3 1323 03334 ,同時滿足 | 32303 3| < p (1) 3 2和3 3不可能同時分別包含a和C,因為在這種情況下,有| 3 23 03 3]>p； ⑵ 如果3 2和⑴3都只包含a (b),即3 23 03 3 = aj (bj ) (j

50、 3都只包含C ,即3 2 3 0 3 3 = Cj(j < p),當i大于1時，3 1 3 2i 3 0 3 3i 3 4中會出現(xiàn)c的個數(shù)大于a的個數(shù)(b的個數(shù))； (3)如果3 2和33分別包含a和b (b和c),當i = 0時3132，033, 34中會出 現(xiàn) a, b 的個數(shù)小于C 的個數(shù)(或a,b 個數(shù)不等) 這些與假設(shè)矛盾, 故 L 不是上下文無關(guān)語言 . ⑵ { ak | k 是質(zhì)數(shù) }; 證明： 假設(shè)L是上下文無關(guān)語言，由泵浦引理，取常數(shù)p,當3cL且131Ap時，可取3 =ak ( kAp 且 kW1 ),將 3 寫為 3 =3132303334 ,同時滿足 | 32

51、303 3| & p , 且 1323 3|=j > 1 ，貝U 當 i=k+1 時，| 3 1 3 2i ⑴ o ⑴ 3i ⑴ 4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且kw 1 ,因此必定不是質(zhì)數(shù)，即3 13 2i 3 03 3i 3 4不屬于L. 這與假設(shè)矛盾, 故 L 不是上下文無關(guān)語言 . ⑶ 由 a,b,C 組成的字符串且是含有a,b,C 的個數(shù)相同的所有字符串 . 證明： 假設(shè)L是上下文無關(guān)語言，由泵浦引理，取常數(shù)p,當3cL且131Ap時，可取 3 = akbkck (k > p),將 3 寫為 3 =313230333

52、4 ,同時滿足 | 32303 3| < p (1)3 2和3 3不可能同時分別包含a和C,因為在這種情況下，有| 3 23 03 3|>p; ⑵ 如果3 2和3 3都只包含a (b或c),即3 2303 3= aj(bj或cj) (j < p), 則當i W 1時，3 1 3 2i 3 0 3 3i 3 4中會出現(xiàn)a,b,c的個數(shù)不再相等； (3)如果3 2和3 3分別包含a和b (b 和c) ,3132i 3033i 34中會出現(xiàn)a,b的 個數(shù)與 c 的不等 ; 這些與假設(shè)矛盾, 故 L 不是上下文無關(guān)語言 . 24 .設(shè)G是Chomsky 范式文法，存在3 c L (G)，

53、求在邊緣為3的推導樹中，最長的路 徑長度與3的長度之間的關(guān)系. 解：設(shè)邊緣為3的推導樹中，最長路徑長度為n,則它與3的長度之間的關(guān)系為|3| 《 2n-1 . 因為由 Chomsky 范式的定義可知 ,Chomsky 范式文法的推導樹都是二叉樹,在最長 路徑長度為n的二叉推導樹中，滿二叉樹推出的句子長度最長，為2n-1,因此3的長度 與其推導樹的最長路徑長度n 的關(guān)系可以用上式表示. 25 . 設(shè)計 PDA 接受下列語言(注意 :不要求 為確定的 ) (1) { 0m1n | m < n }; 解：設(shè) PDA M = ( Q,T, r,B,qo,Zo,F )，其中 Q = {

54、q 0,q1,qf } , T = { 0,1} , r = { 0,1, Z0 }, F = { qf } , B定義如下： B( q。，& , Zo) = { ( qi, Z0 ) }, B( q。,。，Z0 ) = { ( qo, 0Zo ) }, B( q0,0,0 ) = { ( q0, 00 ) }, B( q0,1, Z0 ) = { ( qf, ￡ ) }, B( q0,1,0 ) = { ( qi,￡ ) }, B(qi,1,0 ) = { (qi)}, B (qi, ￡, Z0 ) ={ ( q f, e ) } B(qi,1,Z0 ) = {( qf, ￡) }

55、 B (qf,1,e ) = {( q f, ￡) } (2) { 0min | m >n }; 解：設(shè) PDA M = ( Q,T, r,B,q0,Z0,F )，其中 Q = { q 0,qi,qf } , T = { 0,i} , r = { 0,1, Z0 }, F = { qf } , B定義如下： B( q°, ￡ , Z0 ) = { ( qi, Z0 ) }, B( q0,0, Z0 ) = { ( q0, 0Z0 ) }, B( q0,0,0 ) = { ( q0, 00 ) }, B( q0,1,0 ) = { ( qi,￡ ) }, B( qi,1,0 ) =

56、{ ( qi,￡ ) }, B ( q1, ￡ ,Z0 ) = { ( q f, ￡ ) }, B ( qi, ￡ ,0 ) = { ( q f, ￡ ) } B( qf,1, ￡ ) = { ( qf, ￡ ) } (3) { 0min0m| n 和 m任意}; 解：設(shè) PDA M = ( Q,T, r,B,q0,Z0,F )，其中 Q = { q 0,q1, q2,q3,qf } , T = { 0,1} , r = { 0,1, Z0 }, F = { qf } , B定義如下： B( q0,0, Z0) = { ( q0, 0Z0 ) }, B( q0,0,0 ) = { (

57、 q0, 00 ),( q0, ￡ )}, B( q0,1, Z0 ) = { ( q3, ￡ ) }, B (q3,1,￡) = { (q 3, ￡) }, B (q3, ￡ ,￡ ) = { ( qf,￡) }, B(q0,1,0)= { ( q1,0 )}, B(q1,1,0)= { ( q1,0 )}, B(q1,0,0)= { ( q2/) }, B( q2,0,0 ) = { ( q2/ ) }, B ( q2, ￡ , Z0 ) = { ( q f, e ) }, B ( q0, ￡ , Z0) = { ( q f, e )}nm ? 第五章 1.考慮如下的圖靈

58、機M = ( {q 0, qi, qf, },{0,1},{0,1,B}, B , qo,B,{ qf })，其中 B 定義為： B(qo,0) = {(qi,1,R)} , B(qi,1) = {(q 0,0,R)} , B(qi,B) = {(qf,B,R)}, 非形式化但準確地描述該圖靈機的工作過程及其所接受的語言 . 解：開始時,M的帶上從左端起放有字符串0(10)i (i A0),后跟無限多個空白符 B.M的第一 次動作先讀到第一個0,并改寫為1;然后右移,如果找到第一個1,則改寫為0,并繼續(xù)向 右尋找下一個0,這樣重復進行.當向右尋找1的時候，找到一個空白符B,則結(jié)束. 該圖靈機所接受的語言L(M) = { 0(10) i | i >