《形式语言与自动机》(王柏、杨娟编著)课后习题答案

1、形式语言与自动机课后习题答案第二章4找出右线性文法，能构成长度为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构造上下文无关文法能够产生L=/a,b*且中a的个数是b的两倍答：G=N,T,P,S其中N=S T=a,b P如下:Saab Saba SbaaSaabS SaaSb SaSab SSaabSabaS SabSa SaSba SSabaSbaaS SbaSa SbSaa SSbaa7找出由以下各组生成式产生的语言起始符为S(1) SSaS

2、 Sb(2) SaSb Sc(3) Sa SaE EaS答：1b(ab)n /n0或者L=(ba)nb /n0(2) L=ancbn /n0(3) L=a2n+1 /n0第三章1 以下集合是否为正那么集，假设是正那么集写出其正那么式。（1） 含有偶数个a和奇数个b的a,b*上的字符串集合（2） 含有相同个数a和b的字符串集合（3） 不含子串aba的a,b*上的字符串集合答：1是正那么集，自动机如下奇a偶b偶a偶b a a b b b b奇a奇b偶a奇b a a(2) 不是正那么集，用泵浦引理可以证明，具体见17题2。(3) 是正那么集先看L为包含子串aba的a,b*上的字符串集合显然这是正那么

3、集，可以写出表达式和画出自动机。略那么不包含子串aba的a,b*上的字符串集合L是L的非。根据正那么集的性质，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

4、)*(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*a5.为以下正那么集，构造右线性文法：(1)a,b*(2)以abb结尾的由a和b组成的所有字符串的集合(3)以b为首后跟假设干个a的字符串的集合(4) 含有两个相继a和两个相

5、继b的由a和b组成的所有字符串集合答：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.设正那么集为a(ba)*(1) 构造右线性文法(2) 找出1中文法的有限自 b动机答：1右线性文法G=(S

6、,A,a,b,P,S)P: SaA AbS A2自动机如下：P2P1 ab(p2是终结状态)9.对应图a(b)的状态转换图写出正那么式。图略（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) *

7、(3) q0=aq1+bq2+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.设字母表T=a,b,找出接受以下语言的DFA：（1）

8、 含有3个连续b的所有字符串集合（2） 以aa为首的所有字符串集合（3） 以aa结尾的所有字符串集合答：1M=(q0,q1 q2,q3,a,b,q0,q3),其中如下：abq0q0q1q1q0q2q2q0q3q3q3q32M=(q0,q1 q2 ,a,b,q0,q2),其中如下：abq0q1q1q2q2q2q23M=(q0,q1 q2 ,a,b,q0,q2),其中如下：abq0q1q0q1q2q0q2q2q014构造DFA M1等价于NFA M，NFA M如下：1M=(q0,q1 q2,q3,a,b,q0,q3),其中如下：(q0,a)=q0,q1 (q0,b)=q0(q1,a)=q2 (q1

9、,b)= q2 (q2,a)=q3 (q2,b)= (q3,a)=q3 (q3,b)= q3 2M=(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答：1DFA 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满足a

10、bq0q0,q1 q0q0,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,q32DFA 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,

11、q1,q2,q3,q2,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(起始状态)pqrqpqrr(终止状态)qrp(1) 给出该自动机接收的所有长度为3的串(2) 将此-NFA转换为没有的NFA答：1可被接受的的串共 23个，分别为aac, abc, acc, bac, bbc, bcc, cac, cbc, ccc, caa, cab, c

12、ba, cbb, cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb2-NFA：M=(p,q,r,a,b,c,p,r) 其中如表格所示。因为-closure(p)= 那么设不含的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,r

13、1(q,c)=(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为终止状态)pq b,c a,b,c a,b,c a,b,c c a,b,c b,c a,b,cr a,b,c16设NFA M=(q0,q1,a,b,q0,q1),其中如下：(q0,a)=q0,q1 (q0,b)=q1(q1,a)= (q1,b)= q0, q1构造相应的DFA M1，并进行化简答：构造一个相应的

14、DFA M1=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产生的语言L(G)（2） /a,b*且有相同个数的a和b（3） akcak/k1（4） /a,b*证明：1在L(G)中，a的个数与b的个数相等假设L(G)是正那么集，对于足够大的k取= ak (cb)kc令=102因为|0|>0 |10|k 存在0使10i2L所以对于任意0只能取0=an n(0,k)那么10i

15、2= akn(an)i(cb)kc 在i不等于0时不属于L与假设矛盾。那么L(G)不是正那么集2假设该集合是正那么集，对于足够大的k取= ak bk令=102因为|0|>0 |10|k 存在0使10i2L所以对于任意0只能取0=an n(0,k)那么10i2= akn(an)ibk 在i不等于0时a与b的个数不同，不属于该集合与假设矛盾。那么该集合不是正那么集3假设该集合是正那么集，对于足够大的k取= ak cak令=102因为|0|>0 |10|k 存在0使10i2L所以对于任意0只能取0=an n(0,k)那么10i2= akn(an)icak 在i不等于0时c前后a的个数不同

16、，不属于该集合与假设矛盾。那么该集合不是正那么集4假设该集合是正那么集，对于足够大的k取= ak bakb令=102因为|0|>0 |10|k 存在0使10i2L所以对于任意0只能取0=an n(0,k)那么10i2= akn(an)ibakb 在i不等于0时不满足的形式，不属于该集合与假设矛盾。那么该集合不是正那么集18构造米兰机和摩尔机对于a,b*的字符串，如果输入以bab结尾，那么输出1；如果输入以bba结尾，那么输出2；否那么输出3。答：米兰机：说明状态qaa表示到这个状态时，输入的字符串是以aa结尾。其他同理。 a/3qaaqabb/3a/3 a/3 b/3b/1qbaqbba

17、/2 b/3 摩尔机，状态说明同米兰机。 a aqaba,3 b/3qaab,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 )

18、 ,其中生成式P1如下：S1 | S ,S A1 | A2 ,A1 A3 | A4 ,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变为：S1 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，消除

19、无用符号，得到符合题目要求的等价文法：G1 = ( S1 , a,b,d , P1 , S1 ) ，其中生成式P1为：S1 a | b | d |.11. 设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变换为无生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.解:由算法3，变换为无生成式：N = S 由S ASB得出S ASB | AB ,由A aAS得出A aAS | aA ,由B SBS得出B SBS | SB | BS |B,由SN 得出S

20、1 | S ,因此无的等效文法G1 = ( S1,S,A,B , a,b,d , P1 , 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,因此生成的无单生成式等效

21、文法为G1 = ( S1,S, A,B , a,b , P1 , S1 ) ,其中生成式P1如下：S1 | ASB | AB ,S ASB | AB , A aAS | aA | a , B SBS | SB | BS | aAS | aA | a | bb,由算法1和算法2，消除无用符号(此题没有无用符号);转化为等价的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 | E

22、A | FF, F b ,由此得出符合题目要求的等价文法：G1 = ( S1,S, 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解:将非终结符排序为S,D,S为低位,D为高位,对于D SS ,用S DD | a 代入得 D DDS | aS | b ,用引理4.2.4,变化为D

23、 aS | b | aSD' | bD' , D DS | DSD ,将D生成式代入S生成式得 S aSD | bD | aSDD | bD'D | a ,将D生成式代入D生成式得D aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' ,由此得出等价的Greibach范式文法：G1 = ( S,D,D , a,b , P1 , S ) ,其中生成式P1如下：S aSD | bD | aSDD | bD'D | a ,D aS |

24、 b | aSD' | bD' ,D aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .A1 A3b | A2a , A2 A1b | A2A2a | b , A3 A1a | A3A3b | a解:转化为等价的Chomsky范式的文法:A1 A3A4 | A2A5 ,A2 A1A4 | A2A6 | b ,A3 A1A5 | A3A7 | a ,A4 b ,A5 a ,A6 A2A5 ,A7 A3A4 ,转化为等价的Greibach范式的

25、文法:将非终结符排序为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 A5A4A2 | A6A2 | A5A4 | A6 ,对于A3 A1A5 ,用A1 A3A4 | A2A5代入得A3 A3A4A5 | A2A5A5 | A3A7 | a ,A3生成式右边第一个字符仍是较低位的非终结符,将A2生成式代入A3生成式得A3 A3A4 A5 | A3A4A4 A5A5 | b

26、A5A5 | A3A4A4A2 A5A5 | bA2A5A5 | A3A7 | a ,用引理4.2.4,变化为A3 b A5A5 | bA2A5A5 | a | b A5A5A3 | bA2A5A5A3 | aA3 ,A3 A4A5 | A4A4A5A5 | A4A4A2A5A5 | A7 | A4A5A3 | A4A4A5A5A3 | A4A4A2A5A5A3 | A7A3 ,对于A6 A2A5 ,将A2生成式代入A6生成式得A6 A3A4A4A5 | bA5 | A3A4A4A2A5 | bA2A5 ,A6生成式右边第一个字符仍是较低位的非终结符,将A3生成式代入A6生成式得A6 bA5A

27、5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,对于A7 A3A4 , 将A3生成式代入A7生成式得A7 b A5A5A4 | bA2A5A5A4 | a A4 | b A5A5A3A4 | bA2A5A5A3A4 | aA3A4 ,将A5,A6生成式代入A2

28、生成式得A2 aA4A2 | bA5A5A4A4A5A2 | bA2A5A5A4A4A5A2 | aA4A4A5A2 | bA5A5A3A4A4A5A2 | bA2A5A5A3A4A4A5A2 | aA3A4A4A5A2 | bA5A5A4A4A2A5 A2 | bA2A5A5A4A4A2A5A2 | aA4A4A2A5A2 | bA5A5A3A4A4A2A5A2 | bA2A5A5A3A4A4A2A5A2 | aA3A4A4A2A5A2 | bA2A5A2 | b A5A2 | aA4 | b A5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A

29、4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,将A4,A7生成式代入A3生成式得A3 aA5 | aA4A5A5 | aA4A2A5A5 | aA5A3 | aA4A5A5A3 | aA4A2A5A5A3 | b A5A5A4 | bA2A5A5A4 | aA4 | bA5A5A3A4 | bA2A5A5A3A4 | aA3A4 | bA5A5A4

30、A3 | bA2A5A5A4A3 | a A4A3 | b A5A5A3A4 A3 | bA2A5A5A3A4 A3 | aA3A4A3 ,由此得出等价的Greibach范式文法:G1 = ( S,D,D , a,b , P1 , S ) ,其中生成式P1如下：A1 A3A4 | A2A5 ,A2 A3A4A4 | b | A3A4A4A2 | bA2 ,A3 b A5A5 | bA2A5A5 | a | bA5A5A3 | bA2A5A5A3 | aA3 ,A4 b ,A5 a ,A6 bA5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5

31、 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,A7 b A5A5A4 | bA2A5A5A4 | a A4 | b A5A5A3A4 | bA2A5A5A3A4 | aA3A4 ,A2 aA4A2 | bA5A5A4A4A5A2 | bA2A5A5A4A4A5A2 | aA4A4A5A2 | bA5A5A3A4A4A5A2 | bA2A5A5A3A4A4

32、A5A2 | aA3A4A4A5A2 | bA5A5A4A4A2A5 A2 | bA2A5A5A4A4A2A5A2 | aA4A4A2A5A2 | bA5A5A3A4A4A2A5A2 | bA2A5A5A3A4A4A2A5A2 | aA3A4A4A2A5A2 | bA2A5A2 | bA5A2 | aA4 | b A5A5A4A4A5 | bA2A5A5A4A4A5 | aA4A4A5 | bA5A5A3A4A4A5 | bA2A5A5A3A4A4A5 | aA3A4A4A5 | bA5A5A4A4A2A5 | bA2A5A5A4A4A2A5 | aA4A4A2A5 | bA5A5A3A4A4

33、A2A5 | bA2A5A5A3A4A4A2A5 | aA3A4A4A2A5 | bA2A5 | b A5 ,A3 aA5 | aA4A5A5 | aA4A2A5A5 | aA5A3 | aA4A5A5A3 | aA4A2A5A5A3 | b A5A5A4 | bA2A5A5A4 | aA4 | bA5A5A3A4 | bA2A5A5A3A4 | aA3A4 | bA5A5A4A3 | bA2A5A5A4A3 | a A4 A3 | b A5A5A3A4 A3 | bA2A5A5A3A4 A3 | aA3A4A3 .20. 设文法G有如下得生成式: S aDD , D aS | bS | a

34、, 构造等价的下推自动机.解:根据P162-163的算法,构造下推自动机M,使M按文法G的最左推导方式工作.设M = (Q,T,q0,Z0,F ),其中Q = q0,qf ,T = a,b , = a,b,D,S ,Z0 = S ,F = qf ,定义如下:( q0,S ) = ( q0, aDD ) ,( q0,D ) = ( q0,aS ) , ( q0,bS ) , ( q0,a ) ,( q0,a,a ) = ( q0, ) ,( q0, ) = ( qf, ) .21. 给出产生语言 L = aibjck | i , j , k0 且 i = j 或者 j = k 的上下文无关文法.

35、你给出的文法是否具有二义性?为什么?解: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个数相同时，对于存在两个不同的最左(右)推导。如abcÎL，存在两个不同的最左推导 SÞADÞaAbDÞabDÞabcCÞabc 及SÞEBÞaEBÞaBÞabBcÞabc 。22. 设下推自动机 M = ( q0,q1,a,b,Z0,X, q0, Z0,),其中如下:(q

36、0,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产生的语言 L (G) = L(M).解:在G中,N = q0,Z0,q0, q0,Z0,q1, q0,X,q0, q0,X,q1, q1,Z0,q0, q1,Z0,q1, q1,X,q0, q1,X,q1 .S生成式有S q0,Z0,q0 ,S q0,Z0,q1 ,根据(q0,b, Z0) = (q0, XZ0) ,那么有q

37、0,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 ,q0, X,q1 bq0,X,q1 q1, X,q1 ,因为有(q0,a, X) = (q1, X),那么有q0,X,q0 aq1,X,q0 ,q0,X,q1

38、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产生的语言L(G) = N,T,P,S 其中N = S,q0,Z0,q0,q1,Z0,q0,q1,X,q1, q0,X,q1 ,T = a,b ,生成式P如下:S q0,Z0,q0 ,q0,Z0,q0 bq0,X,q1 q1,Z0,q0 ,q0, X,q1 bq0

39、,X,q1 q1, X,q1 ,q0,X,q1 aq1,X,q1 ,q1,Z0,q0 aq0,Z0,q0 ,q0,Z0,q0 ,q0,Z0,q0 .23. 证明以下语言不是上下文无关语言: anbncm | mn ;证明:假设L是上下文无关语言,由泵浦引理,取常数p,当L且|p时,可取 = apbpcp ,将写为=12034 ,同时满足|203|p2和3不可能同时分别包含a和c,因为在这种情况下,有|203|>p;如果2和3都只包含a (b) ,即203 = aj (bj ) (jp) ,那么当i1时, 12i03i4中会出现a的个数与b的个数不等;如果2和3都只包含c ,即203 =

40、cj (jp),当i大于1时,12i03i4中会出现c的个数大于a的个数 (b的个数);如果2和3分别包含a和b (b和c) ,当i=0时 12i03i4中会出现a, b的个数小于c的个数或a,b个数不等这些与假设矛盾,故L不是上下文无关语言. ak | k是质数 ;证明:假设L是上下文无关语言,由泵浦引理,取常数p,当L且|p时,可取=ak ( kp且k1 ) ,将写为=12034 ,同时满足|203|p ,且|23|=j1 ,那么当i=k+1时,|12i03i4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k1 ,因此必定不是质数,即12i03i4不

41、属于L.这与假设矛盾,故L不是上下文无关语言.由 a,b,c 组成的字符串且是含有 a,b,c 的个数相同的所有字符串.证明:假设L是上下文无关语言,由泵浦引理,取常数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中会出现a,b,c的个数不再相等;如果2和3分别包含a和b (b和c) , 12i03i4中会出现a,b的个数与c的不等;这些与假设矛盾,故L不是上下文无关语言.24. 设G是Chomsky 范式文法,存在 L (G) ，求在边缘为的推导树中,最长的路径长度与的长度之间的关系.解:设边缘为的推导树中,最长路径长度为n,那么它与的长度之间的关系为|2n-1 .