北京邮电大学 自动机 课后习题答案

形式语言与自动机第二章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．找出由下列各组生成式产生的语言（起始符为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）是正则集，自动机如下aabbbbaa(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→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+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和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)此正则集为{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）自动机如下：ab(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+ε=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=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)P1P2=q0=a(ba)*(a+bb)q0+a(ba)*(ba+b)+b(ab)*(aa+b)q0+b(ab)*(ab+a)+a+b=[a(ba)*(a+bb)+b(ab)*(aa+b)]*(a(ba)*(ba+b)+b(ab)*(ab+a)+a+b)10.设字母表T={a,b},找出接受下列语言的DFA：（1）含有3个连续b的所有字符串集合（2）以aa为首的所有字符串集合（3）以aa结尾的所有字符串集合答：（1）M=({q0,q1q2,q3},{a,b},σ,q0,{q3}),其中σ如下：abq0q0q1q1q0q2q2q0q3q3q3q3（2）M=({q0,q1q2},{a,b},σ,q0,{q2}),其中σ如下：abq0q1Φq1q2Φq2q2q2（3）M=({q0,q1q2},{a,b},σ,q0,{q2}),其中σ如下：abq0q1q0q1q2q0q2q2q014构造DFAM1等价于NFAM，NFAM如下：（1）M=({q0,q1q2,q3},{a,b},σ,q0,{q3}),其中σ如下：σ(q0,a)={q0,q1}σ(q0,b)={q0}σ(q1,a)={q2}σ(q1,b)={q2}σ(q2,a)={q3}σ(q2,b)=Φσ(q3,a)={q3}σ(q3,b)={q3}（2）M=({q0,q1q2,q3},{a,b},σ,q0,{q1,q2}),其中σ如下：σ(q0,a)={q1,q2}σ(q0,b)={q1}σ(q1,a)={q2}σ(q1,b)={q1,q2}σ(q2,a)={q3}σ(q2,b)={q0}σ(q3,a)=Φσ(q3,b)={q0}答：（1）DFAM1={Q1,{a,b},σ1,[q0],{[q0,q1,q3]，[q0,q2,q3]，[q0,q1,q2,q3]}其中Q1={[q0],[q0,q1],[q0,q1,q2],[q0,q2],[q0,q1,q2,q3],[q0,q1,q3],[q0,q2,q3],[q0,q3]}σ1满足ab[q0][q0,q1][q0][q0,q1][q0,q1,q2][q0,q2][q0,q1,q2][q0,q1,q2,q3][q0,q2][q0,q2][q0,q1,q3][q0][q0,q1,q2,q3][q0,q1,q2,q3][q0,q2,q3][q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q2,q3][q0,q1,q3][q0,q3][q0,q3][q0,q1,q3][q0,q3]（2）DFAM1={Q1,{a,b},σ1,[q0],{[q1],[q3],[q1,q3],[q0,q1,q2],[q1,q2],[q1,q2,q3],[q2,q3]}其中Q1={[q0],[q1,q3],[q1],[q2],[q0,q1,q2],[q1,q2],[q3],[q1,q2,q3],[q2,q3]}σ1满足ab[q0][q1,q3][q1][q1,q3][q2][q0,q1,q2][q1][q2][q1,q2][q2][q3][q0][q0,q1,q2][q1,q2,q3][q0,q1,q2][q1,q2][q2,q3][q0,q1,q2][q3]Φ[q0][q1,q2,q3][q2,q3][q0,q1,q2][q2,q3][q3][q0]15.15.对下面矩阵表示的ε-NFAεabcP(起始状态)φ{p}{q}{r}q{p}{q}{r}φr(终止状态){q}{r}φ{p}(1)给出该自动机接收的所有长度为3的串(2)将此ε-NFA转换为没有ε的NFA答：（1）可被接受的的串共23个，分别为aac,abc,acc,bac,bbc,bcc,cac,cbc,ccc,caa,cab,cba,cbb,cca,ccb,bba,aca,acb,bca,bcb,bab,bbb,abb（2）ε-NFA：M=({p,q,r},{a,b,c},σ,p,r)其中σ如表格所示。因为ε-closure(p)=Φ则设不含ε的NFAM1=({p,q,r},{a,b,c},σ1,p,r)σ1(p,a)=σ’(p,a)=ε-closure(σ(σ’(p,ε),a))={p}σ1(p,b)=σ’(p,b)=ε-closure(σ(σ’(p,ε),b))={p,q}σ1(p,c)=σ’(p,c)=ε-closure(σ(σ’(p,ε),c))={p,q,r}σ1(q,a)=σ’(q,a)=ε-closure(σ(σ’(q,ε),a))={p,q}σ1(q,b)=σ’(q,b)=ε-closure(σ(σ’(q,ε),b))={p,q,r}σ1(q,c)=σ’(q,c)=ε-closure(σ(σ’(q,ε),c))={p,q,r}σ1(r,a)=σ’(r,a)=ε-closure(σ(σ’(r,ε),a))={p,q,r}σ1(r,b)=σ’(r,b)=ε-closure(σ(σ’(r,ε),b))={p,q,r}σ1(r,c)=σ’(r,c)=ε-closure(σ(σ’(r,ε),c))={p,q,r}图示如下：(r为终止状态)b,cpqa,b,ca,b,ca,b,cca,b,cb,ca,b,ca,b,c16．设NFAM=({q0,q1},{a,b},σ,q0,{q1}),其中σ如下：σ(q0,a)={q0,q1}σ(q0,b)={q1}σ(q1,a)=Φσ(q1,b)={q0,q1}构造相应的DFAM1，并进行化简答：构造一个相应的DFAM1={Q1,{a,b},σ1,[q0],{[q1]，[q0,q1]}其中Q1={[q0]，[q1]，[q0,q1]}σ1满足ab[q0][q0,q1][q1][q1]Φ[q0,q1][q0,q1][q0,q1][q0,q1]由于该DFA已是最简，故不用化简17.使用泵浦引理，证明下列集合不是正则集：（1）由文法G的生成式S→aSbS/c产生的语言L(G)（2）{ω/ω∈{a,b}*且ω有相同个数的a和b}（3）{akcak/k≥1}（4）{ωω/ω∈{a,b}*}证明：（1）在L(G)中，a的个数与b的个数相等假设L(G)是正则集，对于足够大的k取ω=ak(cb)kc令ω=ω1ω0ω2因为|ω0|0|ω1ω0|≤k存在ω0使ω1ω0iω2∈L所以对于任意ω0只能取ω0=ann∈(0,k)则ω1ω0iω2=ak–n(an)i(cb)kc在i不等于0时不属于L与假设矛盾。则L(G)不是正则集（2）假设该集合是正则集，对于足够大的k取ω=akbk令ω=ω1ω0ω2因为|ω0|0|ω1ω0|≤k存在ω0使ω1ω0iω2∈L所以对于任意ω0只能取ω0=ann∈(0,k)则ω1ω0iω2=ak–n(an)ibk在i不等于0时a与b的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（3）假设该集合是正则集，对于足够大的k取ω=akcak令ω=ω1ω0ω2因为|ω0|0|ω1ω0|≤k存在ω0使ω1ω0iω2∈Lr所以对于任意ω0只能取ω0=ann∈(0,k)则ω1ω0iω2=ak–n(an)icak在i不等于0时c前后a的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（4）假设该集合是正则集，对于足够大的k取ωω=ak