资源描述：
《北京邮电大学 自动机 课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机第二章4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。答：G={N,T,P,S}其中N={S,A,B,C,D}T={x,y}其中x∈{所有字母}y∈{所有的字符}P如下:S→xS→xAA→yA→yBB→yB→yCC→yC→yDD→y6．构造上下文无关文法能够产生L={ω/ω∈{a,b}*且ω中a的个数是b的两倍}答：G={N,T,P,S}其中N={S}T={a,b}P如下:S→aabS→abaS→baaS→aabSS→aaSbS→aSabS→SaabS→abaSS→abSaS→aSbaS→SabaS→baaSS→baSaS→bSaaS→Sbaa7．找出由
2、下列各组生成式产生的语言（起始符为S）(1)S→SaSS→b(2)S→aSbS→c(3)S→aS→aEE→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）是正则集，自动机如下奇a偶b偶a偶baabbbb奇a奇b偶a奇baa(2)不是正则集，用泵浦引理可以证明，具体见17题（2）。(3)是正则集先看L’为
3、包含子串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→aAS→BA→abSA→bBB→bB→cCC→DD→bBD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aAS→BA→cCA→bBB→bBB→aC→DC→abBD→d答：(1)由生成式得：S=aA+B①A=abS+bB②B=b+cC③C=D④D=d
4、+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)以ab
5、b结尾的由a和b组成的所有字符串的集合(3)以b为首后跟若干个a的字符串的集合(1)含有两个相继a和两个相继b的由a和b组成的所有字符串集合答：（1）右线性文法G=({S},{a,b},P,S)P:S→aSS→bSS→ε(2)右线性文法G=({S},{a,b},P,S)P:S→aSS→bSS→abb(3)此正则集为{ba*}右线性文法G=({S,A},{a,b},P,S)P:S→bAA→aAA→ε(4)此正则集为{{a,b}*aa{a,b}*bb{a,b}*,{a,b}*bb{a,b}*aa{a,b}*}右线性文法G=({S,A,B,C},{a,b},P,S)P:S→aS/bS/aaA/
6、bbBA→aA/bA/bbCB→aB/bB/aaCC→aC/bC/ε7.设正则集为a(ba)*(1)构造右线性文法(2)找出（1）中文法的有限自动机答：（1）右线性文法G=({S,A},{a,b},P,S)P:S→aAA→bSA→ε（2）自动机如下：P2P1ab(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+ε=q
7、0(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)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)*(
