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

1 形式语言与自动机课后作业答案 第二章 4找出右线性文法，能构成长度为 1 至 5 个字符且以字母为首的字符串。 答： G=N,T,P,S 其中 N=S,A,B,C,D T=x,y 其中 x 所有字母 y 所有的字符 P 如下 : S x S A y A B y B C y C D y 6构造上下文无关文法能够产生 L= / a,b*且 中 a 的个数是 答： G=N,T,P,S 其中 N=S T=a,b P 如下 : S S S S S S S S S S S S 找出由下列各组生成式产生的语言（起始符为 S） (1) S S b (2) S c (3) S a S ：（ 1） b(ab)n /n 0或者 L=(ba)n 0 (2) L=n 0 (3) L= /n 0 第三章 1 下列集合是 否为正则集，若是正则集写出其正则式。 （ 1） 含有偶数个 a 和奇数个 b 的 a,b*上的字符串集合 （ 2） 含有相同个数 a 和 b 的字符串集合 （ 3） 不含子串 a,b*上的字符串集合 答：（ 1）是正则集，自动机如下 a a b b b b a a (2) 不是正则集，用泵浦引理可以证明，具体见 17 题（ 2）。 偶 a 偶 b 偶 a 奇 b 奇 a 奇 b 奇 a 偶 b 2 (3) 是正则集 先看 L为包含子串 a,b*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串 a,b*上的字符串集合 L 是 L的非。 根据正则集的性质， L 也是正则集。 4对下列文法的生成式，找出其正则式 （ 1） G=(S,A,B,C,D,a,b,c,d,P,S),生成式 P 如下： S S B A A b B D D d （ 2） G=(S,A,B,C,D,a,b,c,d,P,S),生成式 P 如下： S S B A A B a C D C d 答： (1) 由生成式得： S= A= B=b+ C=D D=d+ 式化简消去 到 B=b+c(d+即 B=cd+b =B=(cd+b) 将代入 S=ab(cd+b)+(cd+b) =S=( )(cd+b) (2) 由生成式得： S= A=bB+ B=a+ C=D+ D= 由 得 B=b*a 将代入 C=d+a=d+ab+a 将代入 A=b+a+c(d+b+a) 将代入 S=a(b+a+c(d+ab+a)+b*a =ab+a+a+b*a 造右线性文法： (1)a,b* (2)以 尾的由 a 和 b 组成的所有字符串的集合 3 (3)以 b 为首后跟若干个 a 的字符串的集合 (4) 含有两个相继 a 和两个相继 b 的由 a 和 b 组成的所有字符串集合 答：（ 1）右线性文法 G=(S,a,b,P,S) P: S S S (2) 右线性文法 G=(S,a,b,P,S) P: S S S 3) 此正则集为 右线性文法 G=(S,A,a,b,P,S) P: S A A (4) 此正则集为 a,b*aaa,b*bba,b*, a,b*bba,b*aaa,b* 右线性文法 G=(S,A,B,C,a,b,P,S) P: S aS/bS/ aA/bA/ aB/bB/ aC/ a( (1) 构造右线性文法 (2) 找出（ 1）中文法的有限自动机 答：（ 1）右线性文法 G=(S,A,a,b,P,S) P: S A A （ 2）自动机如下： a b (终结状态 ) a） (b)的状态转换图 写出正则式。（图略） （ 1） 由图可知 q0=a+ q1=q0=a =q1=(b+q1+(b+*( =q0=b(b+*( +a+ = q0(a+b (b+* b(b+*aa+a+ =(a+b (b+*(b+*aa+a+ ) =(a+b (b+* (3) q0=a+b q1=b q0=a =q1=ba+b =(ba+b) =q2=ab+a =(ab+a) 2 4 =q0=a(a+ a(ba+b)+b(aa+b)b(ab+a)+a+b =a(a+b(aa+b)* (a(ba+b)+ b(ab+a)+a+b) =a,b,找出接受下列语言的 （ 1） 含有 3 个连续 b 的所有字符串集合 （ 2） 以 首的所有字符串集合 （ 3） 以 尾的所有字符串集合 答：（ 1） M=(q0,q1 q2,a,b, ,其中如下： a b q0 q0 q1 q1 q0 q2 q2 q0 q3 q3 q3 2） M=(q0,q1 ,a,b, ,其中如下： a b q0 q1 q2 q2 3） M=(q0,q1 ,a,b, ,其中如下： a b q0 q1 q0 q1 q2 q0 q2 q2 4 构造 M， M 如下： （ 1） M=(q0,q1 q2,a,b, ,其中如下： (q0,a)=q0, (q0,b)= (q1,a)= (q1,b)= (q2,a)= (q2,b)= (q3,a)= (q3,b)= （ 2） M=(q0,q1 q2,a,b, , q1,其中如下： (q0,a)=q1, (q0,b)= (q1,a)= (q1,b)= q1, (q2,a)= (q2,b)= (q3,a)= (q3,b)= 答：（ 1） a,b, 1, q0,q1, q0,q2, q1,q2, 其中 q0, q0,q1, q0, q0,q2, q0, q0, q0, 1满足 a b q0, q0,q0,q1, q0,q0,q1, q0,q2, q0, 5 q0, q0, q0,q2, q0,q2, q0, q0, q0,q2, q0, q0, q0, q0, q0, q0, q0,（ 2） a,b, 1, q1,q0,q1,q1,q1,q2,q2, 其中 q1, q0,q1,q1, q1,q2,q2, 1满足 a b q1,q1, q0,q1,q1, q0,q1,q1,q2, q0,q1,q1,q2, q0,q1, q1,q2,q2, q0,q1,q2,15. a b c P(起始状态 ) p q r q p q r r(终止状态 ) q r p (1) 给出该自动机接收的所有长度为 3 的串 (2) 将此 换为没有 的 ：（ 1）可被接受的的串共 23 个，分别为 2） M=(p,q,r,a,b,c, ,p,r) 其中 如表格所示。 因为 p)= 则设不含的 1=(p,q,r,a,b,c, 1,p,r) 1(p,a)= (p,a)= ( (p, ),a)=p 1(p,b)= (p,b)= ( (p, ),b)=p,q 1(p,c)= (p,c)= ( (p, ),c)=p,q,r 1(q,a)= (q,a)= ( (q, ),a)=p,q 1(q,b)= (q,b)= ( (q, ),b)=p,q,r 1(q,c)= (q,c)= ( (q, ),c)=p,q,r 1(r,a)= (r,a)= ( (r, ),a)=p,q,r 1(r,b)= (r,b)= ( (r, ),b)=p,q,r 1(r,c)= (r,c)= ( (r, ),c)=p,q,r 图 示如下： (r 为终止状态 ) b,c p q 6 a,b,c a,b,c a,b,c c a,b,c b,c a,b,c a,b,c 16设 M=(q0,a,b, ,其中如下： (q0,a)=q0, (q0,b)= (q1,a)= (q1,b)= 构造相应的 进行化简 答：构造一个相应的 a,b, 1, q0, 其中 q0, 1满足 a b q0, q0,q0,q0,q0,由于该 是最简，故不用化简 明下列集合不是正 则集： （ 1） 由文法 G 的生成式 S c 产生的语言 L(G) （ 2） / a,b*且 有相同个数的 a和 b （ 3） k 1 （ 4） / a,b* 证明：（ 1）在 L(G)中， a 的个数与 b 的个数相等 假设 L(G)是正则集，对于足够大的 k 取 = cb) = 1 0 2 因为 | 0|0 | 1 0| k 存在 0使 1 0 L 所以对于任意 0只能取 0=an n (0,k) 则 1 0= n(an)i(cb) 时不属于 L 与假设矛盾。则 L(G)不是 正则集 （ 2）假设该集合是正则集，对于足够大的 k 取 = ak = 1 0 2 因为 | 0|0 | 1 0| k 存在 0使 1 0 L 所以对于任意 0只能取 0=an n (0,k) 则 1 0= n(an)在 时 a与 属于该集合 与假设矛盾。则 该集合不是正则集 （ 3）假设该集合是正则集，对于足够大的 k 取 = ak = 1 0 2 因为 | 0|0 | 1 0| k 存在 0使 1 0 L r 7 所以对于任意 0只能取 0=an n (0,k) 则 1 0= n(an)在 时 c 前后 a 的个数不同，不属于该集合 与假设矛盾。则 该集合不是正则集 （ 4）假设该集合是正则集，对于足够大的 k 取 = ak = 1 0 2 因为 | 0|0 | 1 0| k 存在 0使 1 0 L 所以对于任意 0只能取 0=an n (0,k) 则 1 0= n(an)在 i 不等于 0时不满足的形式，不属于该集合 与假设矛盾。