资源描述
形式语言与自动机课后习题答案第二章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 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） 含有偶数个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*上的字符串集合显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串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)*(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和两个相继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,A,a,b,P,S)P: SaA AbS A（2）自动机如下：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) *(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） 含有3个连续b的所有字符串集合（2） 以aa为首的所有字符串集合（3） 以aa结尾的所有字符串集合答：（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构造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,q31满足abq0q0,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,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,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, cba, cbb, cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb（2）-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,r1(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，并进行化简答：构造一个相应的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)则10i2= 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的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（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/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 ) ,其中生成式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，消除无用符号，得到符合题目要求的等价文法：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 得出S1 | 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,因此生成的无单生成式等效文法为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 | EA | 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 aS | b | aSD | bD , D DS | DSD ,将D生成式代入S生成式得 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 | 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范式的文法:将非终结符排序为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 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 bA5A5A4A4A5 | 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生成式得A2 aA4A2 | bA5A5A4A4A5A2 | bA2A5A5A4A4A5A2 | aA4A4A5A2 | bA5A5A3A4A4A5A2 | bA2A5A5A3A4A4A5A2 | aA3A4A4A5A2 | bA5A5A4A4A2A5 A2 | bA2A5A5A4A4A2A5A2 | 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,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 A3A4A4 | 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 A5A5A4 | bA2A5A5A4 | a A4 | b A5A5A3A4 | bA2A5A5A3A4 | aA3A4 ,A2 aA4A2 | bA5A5A4A4A5A2 | bA2A5A5A4A4A5A2 | aA4A4A5A2 | bA5A5A3A4A4A5A2 | bA2A5A5A3A4A4A5A2 | aA3A4A4A5A2 | bA5A5A4A4A2A5 A2 | bA2A5A5A4A4A2A5A2 | aA4A4A2A5A2 | bA5A5A3A4A4A2A5A2 | bA2A5A5A3A4A4A2A5A2 | aA3A4A4A2A5A2 | bA2A5A2 | bA5A2 | aA4 | 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 | bA5A5A3A4 | bA2A5A5A3A4 | aA3A4 | bA5A5A4A3 | bA2A5A5A4A3 | a A4 A3 | b A5A5A3A4 A3 | bA2A5A5A3A4 A3 | aA3A4A3 .20. 设文法G有如下得生成式: S aDD , D aS | bS | a , 构造等价的下推自动机.解:根据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 的上下文无关文法.你给出的文法是否具有二义性?为什么?解: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个数相同时，对于存在两个不同的最左(右)推导。如abcL，存在两个不同的最左推导 SADaAbDabDabcCabc 及SEBaEBaBabBcabc 。22. 设下推自动机 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产生的语言 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) ,则有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 ,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产生的语言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,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 = 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不属于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 .因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此的长度与其推导树的最长路径长度n的关系可以用上式表示.25. 设计PDA接受下列语言(注意:不要求为确定的) 0m1n | mn ;解:设PDA M = ( Q,T,q0,Z0,F ),其中Q = q0,q1,qf ,T = 0,1 , = 0,1, Z0 ,F = qf ,定义如下:( q0, , Z0 ) = ( q1, Z0 ) ,( q0,0, Z0 ) = ( q0, 0Z0 ) ,( q0,0,0 ) = ( q0, 00 ) ,( q0,1, Z0 ) = ( qf, ) ,( q0,1, 0 ) = ( q1, ) ,( q1,1, 0 ) = ( q1, ) ,( q1, Z0 ) = ( qf, ) ( q1,1, Z0 ) = ( qf, ) ( qf,1, ) = ( qf, ) 0m1n | mn ;解:设PDA M = ( Q,T,q0,Z0,F ),其中Q = q0,q1,qf ,T = 0,1 , = 0,1, Z0 ,F = qf ,定义如下:( q0, , Z0 ) = ( q1, Z0 ) ,( q0,0, Z0 ) = ( q0, 0Z0 ) ,( q0,0,0 ) = ( q0, 00 ) ,( q0,1, 0 ) = ( q1, ) ,( q1,1, 0 ) = ( q1, ) ,( q1,Z0 ) = ( qf, ) ,( q1,0 ) = ( qf, ) ( qf,1, ) = ( qf, ) 0m1n0m | n和m任意 ;解:设PDA M = ( Q,T,q0,Z0,F ),其中Q = q0,q1, q2,q3,qf ,T = 0,1 , = 0,1, Z0 ,F = qf ,定义如下:( q0,0, Z0 ) = ( q0, 0Z0 ) ,( q0,0,0 ) = ( q0, 00 ),( q0,) ,( q0,1, Z0 ) = ( q3, ) ,( q3,1, ) = (q3,) ,( q3, ) = ( qf, ) ,( q0,1,0 ) = ( q1,0 ) ,( q1,1,0 ) = ( q1,0 ) ,( q1,0,0 ) = ( q2, ) ,( q2,0,0 ) = ( q2, ) ,( q2, Z0 ) = ( qf, ) ,( q0, , Z0 ) = ( qf, )nm 第五章1. 考虑如下的图灵机 M = ( q0, q1, qf, ,0,1,0,1,B, q0,B, qf ),其中定义为:(q0,0) = (q1,1,R) , (q1,1) = (q0,0,R) , (q1,B) = (qf,B,R) ,非形式化但准确地描述该图灵机的工作过程及其所接受的语言.解:开始时,M的带上从左端起放有字符串0(10)i (i0),后跟无限多个空白符B.M的第一次动作先读到第一个0,并改写为1;然后右移,如果找到第一个1,则改写为0,并继续向右寻找下一个0,这样重复进行.当向右寻找1的时候,找到一个空白符B,则结束.该图灵机所接受的语言L(M) = 0(10)i | i
展开阅读全文