北邮形式语言与自动机二三章答案.doc

形式语言与自动机课后作业答案第二章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）中文法的有限自动机答：（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)=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,cc 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不等于1时不属于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不等于1时a与b的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（3）假设该集合是正则集，对于足够大的k取= ak cak令=102因为|0|0 |10|k 存在0使10i2L所以对于任意0只能取0=an n(0,k)则10i2= akn(an)icak 在i不等于1时c前后a的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（4）假设该集合是正则集，对于足够大的k取= ak bakb令=102因为|0|0 |10|k 存在0使10i2L所以对于任意0只能取0=an n(0,k)则10i2= akn(an)ibakb 在i不等于1时不满足的形式，不属于该集合与假设矛盾。则该