《形式語言與自動機》(王柏、楊娟編著)課后習題答案

1、形式語言與自動機課后習題答案第二章4找出右線性文法，能構(gòu)成長度為1至5個字符且以字母為首的字符串。答：G=N,T,P,S其中N=S,A,B,C,D T=x,y 其中x所有字母 y所有的字符 P如下:Sx SxA Ay AyB By ByC Cy CyD Dy6構(gòu)造上下文無關(guān)文法能夠產(chǎn)生L=/a,b*且中a的個數(shù)是b的兩倍答：G=N,T,P,S其中N=S T=a,b P如下:Saab Saba SbaaSaabS SaaSb SaSab SSaabSabaS SabSa SaSba SSabaSbaaS SbaSa SbSaa SSbaa7找出由下列各組生成式產(chǎn)生的語言（起始符為S）(1) SS

2、aS Sb(2) SaSb Sc(3) Sa SaE EaS答：（1）b(ab)n /n0或者L=(ba)nb /n0(2) L=ancbn /n0(3) L=a2n+1 /n0第三章1 下列集合是否為正則集，若是正則集寫出其正則式。（1） 含有偶數(shù)個a和奇數(shù)個b的a,b*上的字符串集合（2） 含有相同個數(shù)a和b的字符串集合（3） 不含子串a(chǎn)ba的a,b*上的字符串集合答：（1）是正則集，自動機如下奇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*上的字符串集合顯然這是正則

3、集，可以寫出表達式和畫出自動機。（略）則不包含子串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如下：SaA SBAabS AbBBb BcCCD DbBDd（2） G=(S,A,B,C,D,a,b,c,d,P,S),生成式P如下：SaA SBAcC AbBBbB BaCD CabBDd答：(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+

4、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*a5.為下列正則集，構(gòu)造右線性文法：(1)a,b*(2)以abb結(jié)尾的由a和b組成的所有字符串的集合(3)以b為首后跟若干個a的字符串的集合(4) 含有兩個相繼a和兩個相繼b的由a和b組成的所有

5、字符串集合答：（1）右線性文法G=(S,a,b,P,S)P: SaS SbS S(2) 右線性文法G=(S,a,b,P,S)P: SaS SbS Sabb(3) 此正則集為ba*右線性文法G=(S,A,a,b,P,S)P: SbA AaA A(4) 此正則集為a,b*aaa,b*bba,b*, a,b*bba,b*aaa,b*右線性文法G=(S,A,B,C,a,b,P,S)P: SaS/bS/aaA/bbB AaA/bA/bbCBaB/bB/aaCCaC/bC/7.設(shè)正則集為a(ba)*(1) 構(gòu)造右線性文法(2) 找出（1）中文法的有限自 b動機答：（1）右線性文法G=(S,A,a,b,P,

6、S)P: SaA AbS A（2）自動機如下：P2P1 ab(p2是終結(jié)狀態(tài))9.對應圖（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+b

7、q2+a+bq1=aq0+bq2+bq0=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為

8、首的所有字符串集合（3） 以aa結(jié)尾的所有字符串集合答：（1）M=(q0,q1 q2,q3,a,b,q0,q3),其中如下：abq0q0q1q1q0q2q2q0q3q3q3q3（2）M=(q0,q1 q2 ,a,b,q0,q2),其中如下：abq0q1q1q2q2q2q2（3）M=(q0,q1 q2 ,a,b,q0,q2),其中如下：abq0q1q0q1q2q0q2q2q014構(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)=q

9、3 (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,q31滿足abq0q0,q1 q0q

10、0,q1q0,q1,q2 q0,q2q0,q1,q2 q0,q1, q2,q3 q0,q2 q0,q2 q0,q1, q3q0 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,q

11、2,q31滿足abq0q1,q3q1q1,q3q2 q0,q1,q2q1q2q1,q2q2q3q0 q0,q1,q2q1,q2,q3 q0,q1,q2q1,q2q2,q3 q0,q1,q2q3q0q1,q2,q3q2,q3 q0,q1,q2q2,q3q3q015. 15.對下面矩陣表示的-NFAabcP(起始狀態(tài))pqrqpqrr(終止狀態(tài))qrp(1) 給出該自動機接收的所有長度為3的串(2) 將此-NFA轉(zhuǎn)換為沒有的NFA答：（1）可被接受的的串共 23個，分別為aac, abc, acc, bac, bbc, bcc, cac, cbc, ccc, caa, cab, cba, cbb,

12、 cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb（2）-NFA：M=(p,q,r,a,b,c,p,r) 其中如表格所示。因為-closure(p)= 則設(shè)不含的NFA M1=(p,q,r,a,b,c,1,p,r)1(p,a)=(p,a)=-closure(p,),a)=p1(p,b)=(p,b)=-closure(p,),b)=p,q1(p,c)=(p,c)=-closure(p,),c)=p,q,r1(q,a)=(q,a)=-closure(q,),a)=p,q1(q,b)=(q,b)=-closure(q,),b)=p,q,r1(q,c)=

13、(q,c)=-closure(q,),c)=p,q,r1(r,a)=(r,a)=-closure(r,),a)=p,q,r1(r,b)=(r,b)=-closure(r,),b)=p,q,r1(r,c)=(r,c)=-closure(r,),c)=p,q,r圖示如下：(r為終止狀態(tài))pq b,c a,b,c a,b,c a,b,c c a,b,c b,c a,b,cr a,b,c16設(shè)NFA M=(q0,q1,a,b,q0,q1),其中如下：(q0,a)=q0,q1 (q0,b)=q1(q1,a)= (q1,b)= q0, q1構(gòu)造相應的DFA M1，并進行化簡答：構(gòu)造一個相應的DFA M1=

14、Q1, a,b,1, q0, q1，q0,q1其中Q1 =q0，q1，q0,q11滿足abq0q0,q1q1q1q0,q1q0,q1q0,q1q0,q1由于該DFA已是最簡，故不用化簡17.使用泵浦引理，證明下列集合不是正則集：（1） 由文法G的生成式SaSbS/c產(chǎn)生的語言L(G)（2） /a,b*且有相同個數(shù)的a和b（3） akcak/k1（4） /a,b*證明：（1）在L(G)中，a的個數(shù)與b的個數(shù)相等假設(shè)L(G)是正則集，對于足夠大的k取= ak (cb)kc令=102因為|0|0 |10|k 存在0使10i2L所以對于任意0只能取0=an n(0,k)則10i2= akn(an)i(

15、cb)kc 在i不等于0時不屬于L與假設(shè)矛盾。則L(G)不是正則集（2）假設(shè)該集合是正則集，對于足夠大的k取= ak bk令=102因為|0|0 |10|k 存在0使10i2L所以對于任意0只能取0=an n(0,k)則10i2= akn(an)ibk 在i不等于0時a與b的個數(shù)不同，不屬于該集合與假設(shè)矛盾。則該集合不是正則集（3）假設(shè)該集合是正則集，對于足夠大的k取= ak cak令=102因為|0|0 |10|k 存在0使10i2L所以對于任意0只能取0=an n(0,k)則10i2= akn(an)icak 在i不等于0時c前后a的個數(shù)不同，不屬于該集合與假設(shè)矛盾。則該集合不是正則集（4

16、）假設(shè)該集合是正則集，對于足夠大的k取= ak bakb令=102因為|0|0 |10|k 存在0使10i2L所以對于任意0只能取0=an n(0,k)則10i2= akn(an)ibakb 在i不等于0時不滿足的形式，不屬于該集合與假設(shè)矛盾。則該集合不是正則集18構(gòu)造米蘭機和摩爾機對于a,b*的字符串，如果輸入以bab結(jié)尾，則輸出1；如果輸入以bba結(jié)尾，則輸出2；否則輸出3。答：米蘭機：說明狀態(tài)qaa表示到這個狀態(tài)時，輸入的字符串是以aa結(jié)尾。其他同理。 a/3qaaqabb/3a/3 a/3 b/3b/1qbaqbba/2 b/3 摩爾機，狀態(tài)說明同米蘭機。 a aqaba,3 b/3q

17、aab,3 b/3qaa,3 b/3 b a a b a bqbab,1 b/3qbb,3 b/3qbba,2 b/3 a b b b 第四章10. 把下列文法變換為無生成式、無單生成式和沒有無用符號的等價文法：S A1 | A2 , A1 A3 | A4 , A2 A4 | A5 , A3 S | b |, A4 S | a，A5 S | d |解:由算法3，變換為無生成式：N = S, A1,A2,A3,A4,A5 G1 = ( S1,S, A1,A2,A3,A4,A5 , a,b,d , P1 , S1 ) ,其中生成式P1如下：S1 | S ,S A1 | A2 ,A1 A3 | A4

18、 ,A2 A4 | A5 ,A3 S | b ,A4 S | a ,A5 S | d ,由算法4，消單生成式：NS1 = S1,S,A1,A2,A3,A4, A5 ,NS = NA1 = NA2 = NA3 = NA4 = NA5 = S, A1,A2,A3,A4, A5 ,運用算法4，則P1變?yōu)椋篠1 a | b | d | ,S a | b | d ,A1 a | b | d ,A2 a | b | d ,A3 a | b | d ,A4 a | b | d ,A5 a | b | d由算法1和算法2，消除無用符號，得到符合題目要求的等價文法：G1 = ( S1 , a,b,d , P1

19、, S1 ) ，其中生成式P1為：S1 a | 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,由SN 得出S1 | S ,因此無的等效文法G1 = ( S1,S,A,B , a,b,d , P

20、1 , S1 ) ,其中生成式P1如下：S1 | S ,S ASB | AB ,A aAS | aA | a,B SBS | SB | BS | B| A | bb ,由算法4，消單生成式：NS1 = S1,S , NS = S , NA = A , NB = A,B 由于S ASB | ABP且不是單生成式,故P1中有S1 | ASB | AB ,同理有 S ASB | AB , A aAS | aA | a , B SBS | SB | BS | aAS | aA | a | bb,因此生成的無單生成式等效文法為G1 = ( S1,S, A,B , a,b , P1 , S1 ) ,其中生

21、成式P1如下：S1 | ASB | AB ,S ASB | AB , A aAS | aA | a , B SBS | SB | BS | aAS | aA | a | bb,由算法1和算法2，消除無用符號(此題沒有無用符號);轉(zhuǎn)化為等價的Chomsky范式的文法:將S1 ASB變換為 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 ,由此得出符合題目要求的等價文法：G1 = ( S1,S,

22、A,B,C,D , a,b , P1 , S1 ) ,其中生成式P1如下：S1 | AC | AB ,S AC | AB , A ED | EA | a , B CS | SB | BS | ED | EA | a | FF ,C SB ,D AS ,E a ,F b .15. 將下列文法變換為等價的Greibach范式文法: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生

23、成式得 S aSD | bD | aSDD | bDD | a ,將D生成式代入D生成式得D aSS | bS | aSDS | bDS | aSS D | bS D | aSDS D | bDS D ,由此得出等價的Greibach范式文法：G1 = ( S,D,D , a,b , P1 , S ) ,其中生成式P1如下：S aSD | bD | aSDD | bDD | a ,D aS | b | aSD | bD ,D aSS | bS | aSDS | bDS | aSS D | bS D | aSDS D | bDS D .A1 A3b | A2a , A2 A1b | A2A2a

24、| b , A3 A1a | A3A3b | a解:轉(zhuǎn)化為等價的Chomsky范式的文法:A1 A3A4 | A2A5 ,A2 A1A4 | A2A6 | b ,A3 A1A5 | A3A7 | a ,A4 b ,A5 a ,A6 A2A5 ,A7 A3A4 ,轉(zhuǎn)化為等價的Greibach范式的文法:將非終結(jié)符排序為A1, A2,A3,A4,A5 ,A1為低位A5為高位,對于A2 A1A4 ,用A1 A3A4 | A2A5代入得A2 A3A4A4 | A2 A5A4 | A2A6 | b ,用引理4.2.4,變化為A2 A3A4A4 | b | A3A4A4A2 | bA2 ,A2 A5A4A

25、2 | A6A2 | A5A4 | A6 ,對于A3 A1A5 ,用A1 A3A4 | A2A5代入得A3 A3A4A5 | A2A5A5 | A3A7 | a ,A3生成式右邊第一個字符仍是較低位的非終結(jié)符,將A2生成式代入A3生成式得A3 A3A4 A5 | A3A4A4 A5A5 | b A5A5 | A3A4A4A2 A5A5 | bA2A5A5 | A3A7 | a ,用引理4.2.4,變化為A3 b A5A5 | bA2A5A5 | a | b A5A5A3 | bA2A5A5A3 | aA3 ,A3 A4A5 | A4A4A5A5 | A4A4A2A5A5 | A7 | A4A5

26、A3 | A4A4A5A5A3 | A4A4A2A5A5A3 | A7A3 ,對于A6 A2A5 ,將A2生成式代入A6生成式得A6 A3A4A4A5 | bA5 | A3A4A4A2A5 | bA2A5 ,A6生成式右邊第一個字符仍是較低位的非終結(jié)符,將A3生成式代入A6生成式得A6 bA5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A

27、5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,對于A7 A3A4 , 將A3生成式代入A7生成式得A7 b A5A5A4 | bA2A5A5A4 | a A4 | b A5A5A3A4 | bA2A5A5A3A4 | aA3A4 ,將A5,A6生成式代入A2生成式得A2 aA4A2 | bA5A5A4A4A5A2 | bA2A5A5A4A4A5A2 | aA4A4A5A2 | bA5A5A3A4A4A5A2 | bA2A5A5A3A4A4A5A2 | aA3A4A4A5A2 | bA5A5A4A4A2A5 A2 | bA2A5A5A4A4A2A5A2 |

28、aA4A4A2A5A2 | bA5A5A3A4A4A2A5A2 | bA2A5A5A3A4A4A2A5A2 | aA3A4A4A2A5A2 | bA2A5A2 | b A5A2 | aA4 | b A5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,將A4,

29、A7生成式代入A3生成式得A3 aA5 | aA4A5A5 | aA4A2A5A5 | aA5A3 | aA4A5A5A3 | aA4A2A5A5A3 | b A5A5A4 | bA2A5A5A4 | aA4 | bA5A5A3A4 | bA2A5A5A3A4 | aA3A4 | bA5A5A4A3 | bA2A5A5A4A3 | a A4A3 | b A5A5A3A4 A3 | bA2A5A5A3A4 A3 | aA3A4A3 ,由此得出等價的Greibach范式文法:G1 = ( S,D,D , a,b , P1 , S ) ,其中生成式P1如下：A1 A3A4 | A2A5 ,A2 A3

30、A4A4 | b | A3A4A4A2 | bA2 ,A3 b A5A5 | bA2A5A5 | a | bA5A5A3 | bA2A5A5A3 | aA3 ,A4 b ,A5 a ,A6 bA5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,A7 b A5

31、A5A4 | bA2A5A5A4 | a A4 | b A5A5A3A4 | bA2A5A5A3A4 | aA3A4 ,A2 aA4A2 | bA5A5A4A4A5A2 | bA2A5A5A4A4A5A2 | aA4A4A5A2 | bA5A5A3A4A4A5A2 | bA2A5A5A3A4A4A5A2 | aA3A4A4A5A2 | bA5A5A4A4A2A5 A2 | bA2A5A5A4A4A2A5A2 | aA4A4A2A5A2 | bA5A5A3A4A4A2A5A2 | bA2A5A5A3A4A4A2A5A2 | aA3A4A4A2A5A2 | bA2A5A2 | bA5A2 | aA

32、4 | b A5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,A3 aA5 | aA4A5A5 | aA4A2A5A5 | aA5A3 | aA4A5A5A3 | aA4A2A5A5A3 | b A5A5A4 | bA2A5A5A4 | aA4 | bA5

33、A5A3A4 | bA2A5A5A3A4 | aA3A4 | bA5A5A4A3 | bA2A5A5A4A3 | a A4 A3 | b A5A5A3A4 A3 | bA2A5A5A3A4 A3 | aA3A4A3 .20. 設(shè)文法G有如下得生成式: S aDD , D aS | bS | a , 構(gòu)造等價的下推自動機.解:根據(jù)P162-163的算法,構(gòu)造下推自動機M,使M按文法G的最左推導方式工作.設(shè)M = (Q,T,q0,Z0,F ),其中Q = q0,qf ,T = a,b , = a,b,D,S ,Z0 = S ,F = qf ,定義如下:( q0,S ) = ( q0, aDD )

34、,( q0,D ) = ( q0,aS ) , ( q0,bS ) , ( q0,a ) ,( q0,a,a ) = ( q0, ) ,( q0, ) = ( qf, ) .21. 給出產(chǎn)生語言 L = aibjck | i , j , k0 且 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 |文法具有二義性。因為當句子中a,b,c個數(shù)相同時，對于存在兩個不同的最左(右)推導。如abcL，存在兩個不同的最左推導 SAD

35、aAbDabDabcCabc 及SEBaEBaBabBcabc 。22. 設(shè)下推自動機 M = ( q0,q1,a,b,Z0,X, q0, Z0,),其中如下:(q0,b, Z0) = (q0, XZ0) ,(q0, Z0) = (q0, ) ,A(q0,b, X) = (q0, XX) , (q1,b, X) = (q1, ) ,(q0,b, X) = (q1, X) , (q1,a, Z0) = (q0, Z0) ,試構(gòu)造文法G產(chǎn)生的語言 L (G) = L(M).解:在G中,N = q0,Z0,q0, q0,Z0,q1, q0,X,q0, q0,X,q1, q1,Z0,q0, q1,Z0

36、,q1, q1,X,q0, q1,X,q1 .S生成式有S q0,Z0,q0 ,S q0,Z0,q1 ,根據(jù)(q0,b, Z0) = (q0, XZ0) ,則有q0,Z0,q0 bq0,X,q0 q0,Z0,q0 ,q0,Z0,q0 bq0,X,q1 q1,Z0,q0 ,q0,Z0,q1 bq0,X,q0 q0,Z0,q1 ,q0,Z0,q1 bq0,X,q1 q1,Z0,q1 ,因為有(q0,b, X) = (q0, XX),則有q0,X,q0 bq0,X,q0 q0,X,q0 ,q0, X,q0 bq0,X,q1 q1, X,q0 ,q0, X,q1 bq0,X,q0 q0, X,q1 ,

37、q0, X,q1 bq0,X,q1 q1, X,q1 ,因為有(q0,a, X) = (q1, X),則有q0,X,q0 aq1,X,q0 ,q0,X,q1 aq1,X,q1 ,因為有(q1,a, Z0) = (q0, Z0),則有q1,Z0,q0 aq0,Z0,q0 ,q1,Z0,q1 aq0,Z0,q1 ,因為有(q0, Z0) = (q0, ),則有q0,Z0,q0 ,因為有(q1,b, X) = (q1, ),則有q1,X,q1 利用算法1和算法2,消除無用符號后,得出文法G產(chǎn)生的語言L(G) = N,T,P,S 其中N = S,q0,Z0,q0,q1,Z0,q0,q1,X,q1, q

38、0,X,q1 ,T = a,b ,生成式P如下:S q0,Z0,q0 ,q0,Z0,q0 bq0,X,q1 q1,Z0,q0 ,q0, X,q1 bq0,X,q1 q1, X,q1 ,q0,X,q1 aq1,X,q1 ,q1,Z0,q0 aq0,Z0,q0 ,q0,Z0,q0 ,q0,Z0,q0 .23. 證明下列語言不是上下文無關(guān)語言: anbncm | mn ;證明:假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當L且|p時,可取 = apbpcp ,將寫為=12034 ,同時滿足|203|p2和3不可能同時分別包含a和c,因為在這種情況下,有|203|p;如果2和3都只包含a (b) ,

39、即203 = aj (bj ) (jp) ,則當i1時, 12i03i4中會出現(xiàn)a的個數(shù)與b的個數(shù)不等;如果2和3都只包含c ,即203 = cj (jp),當i大于1時,12i03i4中會出現(xiàn)c的個數(shù)大于a的個數(shù) (b的個數(shù));如果2和3分別包含a和b (b和c) ,當i=0時 12i03i4中會出現(xiàn)a, b的個數(shù)小于c的個數(shù)（或a,b個數(shù)不等）這些與假設(shè)矛盾,故L不是上下文無關(guān)語言. ak | k是質(zhì)數(shù) ;證明:假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當L且|p時,可取=ak ( kp且k1 ) ,將寫為=12034 ,同時滿足|203|p ,且|23|=j1 ,則當i=k+1時,|

40、12i03i4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k1 ,因此必定不是質(zhì)數(shù),即12i03i4不屬于L.這與假設(shè)矛盾,故L不是上下文無關(guān)語言.由 a,b,c 組成的字符串且是含有 a,b,c 的個數(shù)相同的所有字符串.證明:假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)p,當L且|p時,可取 = akbkck (kp) ,將寫為=12034 ,同時滿足|203|p2和3不可能同時分別包含a和c,因為在這種情況下,有|203|p;如果2和3都只包含a (b或c) ,即203 = aj (bj或cj ) (jp) ,則當i1時, 12i03i4中會出現(xiàn)a,b,c的個數(shù)不再相等;如果2和3分別包含a和b (b和c) , 12i03i4中會出現(xiàn)a,b的個數(shù)與c的不等;這些與假設(shè)矛盾,故L不是上下文無關(guān)語言.24. 設(shè)G是Chomsky 范式文法,存在 L (G) ，求在邊緣為的推導樹中,最長的路徑長度與的長度之間的關(guān)系.解:設(shè)邊緣為的推導樹中,最長路徑長度為n,則它與的長度之間的關(guān)系為|2n-1 .因為由Chomsky范式的定義