形式语言与自动机课后习题答案第二章4．找出右线性文法，能构成长度为1 至 5 个字符且以字母为首的字符串。答： G={N,T,P,S}其中 N={S,A,B,C,D} T={x,y} 其中 x∈{所有字母 } y∈{所有的字符 } P 如下 :S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y6．构造上下文无关文法能够产生L={ω / ω ∈ {a,b}* 且ω 中 a 的个数是 b 的两倍 }答： G={N,T,P,S}其中 N={S} T={a,b} P如下 :S→aab S→aba S→baaS→aabS S→ aaSb S→aSab S→SaabS→abaS S→ abSa S→aSba S→SabaS→baaS S→ baSa S→bSaa S→Sbaa7．找出由下列各组生成式产生的语言（起始符为S）(1) S→SaS S→b(2) S→aSb S→c(3) S→a S→aE E→aS答：（ 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）是正则集，自动机如下aab b b baa(2) 不是正则集，用泵浦引理可以证明，具体见17 题（ 2）。偶 a 偶 b偶 a 奇 b奇 a 奇 b奇 a 偶 b(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 如下：S→aA S→BA→abS A→bBB→b B→cCC→D D→bBD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式 P 如下：S→aA S→BA→cC A→bBB→bB B→ aC→D C→abBD→d答： (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...
VIP
