形式语言与自动机课后习题答案

1、形式语言与自动机课后作业答案第二章4找出右线性文法，能构成长度为 1 至 5 个字符且以字母为首的字符串。答：G=N,T,P,S其中 N=S,A,B,C,D T=x,y 其中 x 所有字母 y 所有的字符4 x Sf xAA f yA f yB4 y BfyCCfy CfyDDfy 6 构造上下文无关文法能够产生L=3/a,b*且3中 a 的个数是 b 的两倍答: G=N,T,P,S其中 N=S T=a,b P 如下：Sfaab Sfaba SfbaaSfaabS SfaaSbSfaSabSfSaabSfabaS SfabSaSfaSbaSfSabaSfbaaS SfbaSaSfbSaaSfS

2、baa7 找出由下列各组生成式产生的语言(起始符为S)SfSaS SfbSfaSb Sfc(3) Sfa SfaE EfaS答：(1) b(ab)n/n 0或者 L=(ba)nb /n 0(2) L=ancbn/n 0(3) L=a2n+1/n 0第三章1.下列集合是否为正则集，若是正则集写出其正则式。(1)含有偶数个 a 和奇数个 b 的a,b*上的字符串集合(2)含有相同个数 a 和 b 的字符串集合(3)不含子串 aba 的a,b*上的字符串集合答：(1)是正则集，自动机如下P 如下:(3) 是正则集先看 L 为包含子串 aba 的a,b*上的字符串集合 显然这是正则集，可以写出表达式和

3、画出自动机。(略) 则不包含子串 aba 的a,b*上的字符串集合 L 是L的非。 根据正则集的性质，L 也是正则集。4对下列文法的生成式，找出其正则式(1)G=(SAB,C,D,a,b,c,d,P,S), 生成式 P 如下：SfaA SBAfabS AbBBfb BfcCCfD DfbBDfd(2)G=(SAB,C,D,a,b,c,d,P,S), 生成式 P 如下：SfaA SfBAfcC AfbBBfbB BfaCfD CfabBDfd答： (1) 由生成式得：S=aA+B A=abS+bB B=b+cC C=D D=d+bB 式化简消去 CD 得到 B=b+c(d+bB)即 B=cbB+

4、cd+b =B=(cb)*(cd+b)将代入b bb b不是正则集，用泵浦引理可以证明，具体见 17 题(2)S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =S=(aab)*(ab+& )(cb)*(cd+b)(2) 由生成式得：S=aA+B A=bB+cCB=a+bB C=D+abBD=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+acaba+b*a5. 为下列正则集，构造右线性文法：(1)a,b*(2)以 abb 结尾的由 a 和 b

5、 组成的所有字符串的集合(3)以 b 为首后跟若干个 a 的字符串的集合(4)含有两个相继 a 和两个相继 b 的由 a 和 b 组成的所有字符串集合 答：(1)右线性文法G=(S,a,b,P,S)P: SfaS SfbS S(2)右线性文法 G=(S,a,b,P,S)P: SfaS SfbS Sfabb(3)此正则集为ba*右线性文法 G=(S,A,a,b,P,S)P: SfbA AfaA Af(4)此 正 则 集 为 a,b*aaa,b*bba,b*,a,b*bba,b*aaa,b*右 线 性 文 法G=(SAB,C,a,b,P,S)P: SfaS/bS/aaA/bbBAfaA/bA/bb

6、CBfaB/bB/aaCCfaC/bC/&7.设正则集为 a(ba)*(1)构造右线性文法找出(1)中文法的有限自动机答：(1)右线性文法 G=(S,A,a,b,P,S)P: SfaA AfbS Af&(2)自动机如下：(p2 是终结状态)9.对应图(a) (b)的状态转换图写出正则式。(图略)(1)由图可矢廿 qo=aqo+bq1+a+&q1=aq2+bq1qo=aqo+bq+a=q1=abq1+bq1+aaqo+aa=(b+ab) q1+aaqo+aa=(b+ab) *( aaq0+aa)=q0=aqo+b(b+ab) *( aaqo+aa ) +a+ &=

7、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) qo=aq1+bq2+a+bq1=aqo+bq2+bqo=aq1+bqo+a=q1=aqo+baq1+bbqo+ba+b=(ba)*(aq0+bbqo+ba+b)=q2=aaqo+abq2+bqo+ab+a=(ab)*(aaq0+bq0+ ab+a)=qo=a(ba)*(a+bb) q0+ a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab+a)+a+b=a(ba)

8、*(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=(qo,qiq2,q3,a,b, o ,qo,q3),其中如下:abqoqoq1q1qoq2q2qoq3q3q3q3(2) M=(qo,qq ,a,b,o,qo,q2),其中o如下:abqoq1q1q2q2q2q2(3) M=(qo,qiq2,a,b,o,qo,q2),其中o如下:abq。q1q。q1q

9、2q。q2q2qo14 构造 DFA Mi等价于 NFA M, NFA M 如下：(1)M=(qo,q1q2,q3,a,b,o,qo,q3),其中o如下：o(qo,a)=qo,q1o(qo,b)=qoo(q1,a)=q2o(q1,b)= q2o(q2,a)=q3o(q2,b)=o(q3,a)=q3o(q3,b)= q3(2)M=(qo,q1q2,q3,a,b,o,qo, q1,q2),其中o如下：o(qo,a)=q1,q2o(qo,b)=q1o(q1,a)=q2o(q1,b)= q14o(q2,a)=q3o(q2,b)= qoo(q3,a)= o(q3,b)= qo答：(1)DFA M=Q,

10、a,b,o1, qo, qo,q1,q3,qo,q2,q3,qo, q1,q2,q3其中 Q =qo,qo,q1,qo,q1,q2,qo,q2,qo,q1,q2,q3,qo,q1, q3,qo,q2,q3, qo,q3o1满足abqoqo,q1qoqo,q1qo,q1,q2qo,q2q0,q1,q2q0,q1, q2,q3q0,q2q0,q2q0,q1, q3q0q0,q1, q2加q0,q1, q2皿q0,q2, q3q0,q1, q3q0,q1, q2心q0,q2, q3q0,q2, q3q0,q1, q3q0,q3q0,q3q0,q1, q3q0,q3(2) DFAM=Qi,a,b,1,

11、 q。,qi,q3,qi,q3,qo,qi,q2,qi,q2 ,qi,q2,q3,q2,q3其中 Q =qo,qi,q3, qi,q2, qo,qi,q2,qi,q2,q3, qi,q2,q3,q2,q31满足abq0q1,q3q1q1,q3q2q0,q1,q2q1q2q1,q2q2q3q0q0,q1,q2q1,q2,q3q0,q1,q2q1,q2q2,q3q0,q1,q2q3q0q1,q2,q3q2,q3q0,q1,q2q2,q3q3q015. 15.对下面矩阵表示的& -NFAabcP（起始状态）0pqrqPqr0r（终止状态）qr0p(1) 给出该自动机接收的所有长度为3 的串(

12、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 M=(p,q,r,a,b,c,1,p,r)1(p,a)=(p,a)= -closure(p, ),a)=p1(P,b)=(p,b

13、)= -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 为终止状态）16.设 NFA M=(

14、qo,qi,a,b, o ,qo,qi),其中厅如下： (qo,a)=qo,q1 o (qo,b)=q1o (qi,a)= o (qi,b)= q0, q1构造相应的 DFA M1,并进行化简答：构造一个相应的 DFA M1=Q1, a,b,o1, qo, q1 , qo,q(|其中 Q =q0 , q1, qo,q1o1满足abq0q0,q1q1q1q0,q1q0,q1q0,q1q0,q1由于该 DFA 已是最简，故不用化简17.使用泵浦引理，证明下列集合不是正则集：(1)由文法 G 的生成式 S- aSbS/c 产生的语言 L(G)(2)3/a,b*且3有相同个数的 a 和 bk k(3)

15、aca/k 1(4)33/a,b*证明：(1)在 L(G)中，a 的个数与 b 的个数相等 假设 L(G)是正则集，对于足够大的 k 取3= ak(cb)kc 令3=313032因为|3o|O |313o|Wk 存在30使313032 L所以对于任意30只能取30=ann (0,k) 则313J32= ak-n(an)i(cb)kc 在 i 不等于 0 时不属于 L 与假设矛盾。则 L(G)不是正则集(2)假设该集合是正则集，对于足够大的k 取3= akbk令3=313032因为|3o|O |313o|Wk 存在30使313032 L所以对于任意30只能取30=ann (0,k) 则313 0 32= ak-n(an)ibk在 i 不等于 0 时 a 与 b 的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集(3)假设该集合是正则集，对于足够大的k 取3= akcak令3=3130CO2因为|3o|O |313o|Wk 存在30使313032 L所以对于任意3o只能取3o=ann (0,k)则313oi32= ak-n(an)icak在 i 不等于 0 时 c 前后 a 的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集(4)假设该集合是正则集，对于足够大的k 取33= akbakb令3 3=313032因为