您好,欢迎访问三七文档
当前位置:首页 > 机械/制造/汽车 > 机械/模具设计 > 《形式语言与自动机》(王柏杨娟编著)北邮_课后习题答案
北京邮电大学——形式语言与自动机课后作业答案第二章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)中文法的有限自b动机答:(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)假设该集合是正则
本文标题:《形式语言与自动机》(王柏杨娟编著)北邮_课后习题答案
链接地址:https://www.777doc.com/doc-2836829 .html