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

《形式语言与自动机课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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→aba

2、SS→abSaS→aSbaS→SabaS→baaSS→baSaS→bSaaS→Sbaa7．找出由下列各组生成式产生的语言（起始符为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

3、）是正则集，自动机如下(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→aAS→BA→abSA→bBB→bB→cCC→DD→bBD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生

4、成式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+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+

5、abb*a=d+ab+a⑦++将⑥⑦代入②A=ba+c(d+ba)⑧++将⑥⑧代入①S=a(ba+c(d+aba))+b*a=ab+a+acd+acab+a+b*a5.为下列正则集，构造右线性文法：(1){a,b}*(2)以abb结尾的由a和b组成的所有字符串的集合(3)以b为首后跟若干个a的字符串的集合(4)含有两个相继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)此正

6、则集为{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/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）自动机如下：9.

7、对应图（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+ε=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)q0=aq1+bq2+a+bq1=aq0+bq2+bq0

8、=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)