《形式语言与自动机课后习题答案》由会员分享，可在线阅读，更多相关《形式语言与自动机课后习题答案（7页珍藏版）》请在金锄头文库上搜索。
1、形式语言与自动机课后作业答案第二章4找出右线性文法，能构成长度为 1 至 5 个字符且以字母为首的字符串。答：G=N,T,P,S其中 N=S,A,B,C,D T=x,y 其中 x所有字母 y所有的字符 P 如下:S x SxA Ay AyB By ByC Cy CyD Dy6构造上下文无关文法能够产生L=/a,b*且 中 a 的个数是 b 的两倍答：G=N,T,P,S其中 N=S T=a,b P 如下:S aab Saba SbaaS aabS SaaSb SaSab SSaabS abaS SabSa SaSba SSabaS baaS SbaSa SbSaa SSbaa7找出由下列各组生成
2、式产生的语言（起始符为 S）(1) S SaS 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）是正则集，自动机如下 aab b b baa(2) 不是正则集，用泵浦引理可以证明，具体见 17 题（2）。(3) 是正则集先看 L为包含子串 aba
3、 的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) 由生成式得：偶 a 偶b偶 a 奇b奇 a 奇b奇 a 偶bS=aA+B A=abS+bB B=b+cC C=D
4、 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 结尾的由
5、 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/bbCB
6、aB/bB/aaCCaC/bC/7.设正则集为 a(ba)*(1) 构造右线性文法(2) 找出（1）中文法的有限自动机答：（1）右线性文法 G=(S,A,a,b,P,S)P: SaA AbS A（2）自动机如下：ab(p2 是终结状态)9.对应图（a）(b)的状态转换图写出正则式。（图略）（1） 由图可知 q0=aq0+bq1+a+q1=aq2+bq1q0=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)+
7、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)*
8、(ba+b)+ b(ab)*(ab+a)+a+b)10.设字母表 T=a,b,找出接受下列语言的 DFA：（1） 含有 3 个连续 b 的所有字符串集合P1 P2（2） 以 aa 为首的所有字符串集合（3） 以 aa 结尾的所有字符串集合答：（1）M=(q 0,q1 q2,q3,a,b,q 0,q3),其中 如下：a bq0 q0 q1q1 q0 q2q2 q0 q3q3 q3 q3（2）M=(q 0,q1 q2 ,a,b,q 0,q2),其中 如下：a bq0 q1 q1 q2 q2 q2 q2（3）M=(q 0,q1 q2 ,a,b,q 0,q2),其中 如下：a bq0 q1 q0q1
9、q2 q0q2 q2 q014 构造 DFA M1 等价于 NFA M，NFA M 如下：（1）M=(q 0,q1 q2,q3,a,b,q 0,q3),其中 如下：(q 0,a)=q0,q1 (q 0,b)=q0(q 1,a)=q2 (q 1,b)= q2 (q 2,a)=q3 (q 2,b)= (q 3,a)=q3 (q 3,b)= q3 （2）M=(q 0,q1 q2,q3,a,b,q 0, q1,q2),其中 如下：(q 0,a)=q1,q2 (q 0,b)=q1(q 1,a)=q2 (q 1,b)= q1,q2 (q 2,a)=q3 (q 2,b)= q0(q 3,a)= (q 3,b
10、)= q0答：（1）DFA M1=Q1, a,b, 1, q0, q0,q1,q3，q 0,q2,q3，q 0, q1,q2,q3其中 Q1 =q0,q0,q1, q0,q1,q2, q0,q2, q0,q1, q2,q3, q0,q1, q3, q0,q2, q3, q0,q3 1 满足a bq0 q0,q1 q0q0,q1 q0,q1,q2 q0,q2q0,q1,q2 q0,q1, q2,q3 q0,q2 q0,q2 q0,q1, q3 q0 q0,q1, q2,q3 q0,q1, q2,q3 q0,q2, q3 q0,q1, q3 q0,q1, q2,q3 q0,q2, q3 q0,q2
11、, 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,q3 1 满足a bq0 q1,q3 q1q1,q3 q2 q0,q1,q2q1 q2 q1,q2q2 q3 q0 q0,q1,q2 q1,q2,q3 q0,q1,q2q1,q2 q2,q3 q0,q1,q2q3 q0q1,q2,q3 q2,q3 q0,q1,q2q2
12、,q3 q3 q015. 15.对下面矩阵表示的 -NFA a b cP(起始状态) p q rq p q r r(终止状态) q r p(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
13、(p)= 则设不含 的 NFA M1=(p,q,r,a,b,c, 1,p,r) 1(p,a)=(p,a)=-closure(p,),a)=p 1(p,b)=(p,b)=-closure( (p,),b)=p,q 1(p,c)=(p,c)=-closure(p,),c)=p,q,r 1(q,a)=(q,a)=-closure(q,),a)=p,q 1(q,b)=(q,b)=-closure(q,),b)=p,q,r 1(q,c)=(q,c)=-closure(q,),c)=p,q,r 1(r,a)=(r,a)=-closure( (r,),a)=p,q,r 1(r,b)=(r,b)=-closure(r,),b)=p,q,r 1(r,c)=(r,c)=-closure(r,),c)=p,q,r图示如下：(r 为终止状态)b,ca,b,c a,b,c a,b,cc a,b,c b,c a,b,ca,b,c16设 NFA M=(q0,q1,a,b,q 0,q1),其中 如下：(q 0,a)=q0,q1 (q 0,b)=q1(q 1,a)= (q 1,b)= q0, q1构造相应的 DFA M1，并进行化简答：构造一个相应的 DF
