形式语言与自动机课后习题答案
第二章
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→y
6．构造上下文无关文法能够产生
L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S}
7．找出由下列各组生成式产生的语言（起始符为S） (1) S→SaS S→b (2) S→aSb S→c (3) S→a S→aE E→aS
答：（1）b(ab)/n≥0}或者L={(ba)b/n≥0}
(2) L={acb/n≥0} (3) L={a2n+1 /n≥0} 第三章
1． 下列集合是否为正则集，若是正则集写出其正则式。
（1） 含有偶数个a和奇数个b的{a,b}*上的字符串集合
n
n n
n
其中N={S} T={a,b} P如下: S→aab S→aba S→baa
S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa
（2） 含有相同个数a和b的字符串集合 （3） 不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 偶a偶b a a
b b b b
a 偶a奇b
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如下：
S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d
（2） G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：
奇a奇b 奇a偶b S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→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+aba ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a
=aba+acd+acaba+b*a
+
++
形式语言与自动机课后习题答案
