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

形式语言与自动机第二章4.找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。答：G={Ｎ,T,Ｐ，S}ﻩ其中N={Ｓ,Ａ，B,C，D}Ｔ={ｘ,ｙ｝其中x∈{所有字母}y∈{所有的字符｝P如下: S→xS→xＡA→yA→yBB→yB→yCＣ→yＣ→yDＤ→ｙ6．构造上下文无关文法可以产生Ｌ={ω/ω∈{a,b}＊且ω中ａ的个数是ｂ的两倍｝答:G={N,T,P，S}ﻩ其中Ｎ={S}T={a,b｝Ｐ如下： Ｓ→aaｂＳ→abaS→baa S→ａａｂSＳ→aａSbＳ→aＳaｂS→SaabﻩS→ａbaSS→abSaS→aSbaS→SａbaﻩS→ｂaaSS→baSaS→bSaaS→Ｓbaa７．找出由下列各组生成式产生的语言（起始符为S)Ｓ→SaSS→bS→aSbS→cS→aS→aEE→aS答：（１)b(aｂ）ｎ/n≥0}或者Ｌ=｛(ba)nb/ｎ≥0}(２)L＝｛ancbn/n≥０}（3)Ｌ={ａ2n＋１/ｎ≥０}第三章下列集合是否为正则集,若是正则集写出其正则式。具有偶数个a和奇数个b的{a,b}＊上的字符串集合具有相同个数a和b的字符串集合不含子串aｂa的｛a,b｝*上的字符串集合答：（１）是正则集，自动机如下奇a偶b偶a偶b奇a偶b偶a偶baabbbb奇a奇b偶a奇ba奇a奇b偶a奇ba(2)不是正则集,用泵浦引理可以证明，具体见17题（2）。(3）是正则集 先看L’为包含子串aｂａ的{a,b｝*上的字符串集合ﻩ显然这是正则集，可以写出表达式和画出自动机。（略)ﻩ则不包含子串aｂa的{ａ，b}*上的字符串集合L是L’的非。根据正则集的性质,L也是正则集。4.对下列文法的生成式,找出其正则式G＝(｛Ｓ,Ａ，B,C,Ｄ｝,{a,b，c，ｄ｝，Ｐ,Ｓ),生成式P如下:S→ａAS→BA→abSA→bＢB→bＢ→cＣC→DD→ｂBＤ→dG=(｛Ｓ,A,Ｂ,C,D},｛a,b，ｃ,d},P，S),生成式P如下:Ｓ→ａAS→BＡ→cＣA→bBB→bＢＢ→ａＣ→DC→abBＤ→d答:(1）由生成式得： S=aA＋Ｂ①Ａ=ａbS＋ｂB②B=b+cＣ③Ｃ=D④D=d+ｂB⑤③④⑤式化简消去ＣD,得到B=b+c（ｄ+ｂＢ）即Ｂ＝cbB+cd＋ｂ＝>Ｂ=(cb)*（ｃｄ+ｂ)⑥将②⑥代入①Ｓ＝aａｂS＋ａb(cb)*(cｄ+ｂ)+(cb)＊（cd＋b）=>S=（aａb)*（ab+ε)(ｃｂ)*(ｃd＋b)（2）由生成式得： Ｓ=aA+B①Ａ=ｂB+cC②B=a+bＢ③C＝D+abＢ④D=dB⑤由③得B＝b*a⑥将⑤⑥代入④C＝ｄ+aｂb＊a＝d+ab+a⑦将⑥⑦代入②A＝ｂ+a+c(d＋b+a）⑧将⑥⑧代入①Ｓ＝a(b+a+c(d+ab+a))+ｂ*a ﻩﻩ＝ab＋ａ＋aｃｄ+acab＋a+ｂ*a5.为下列正则集,构造右线性文法：(1）{ａ,b}＊(２)以aｂb结尾的由a和b组成的所有字符串的集合(3)以b为首后跟若干个a的字符串的集合具有两个相继a和两个相继b的由a和b组成的所有字符串集合答:(1）右线性文法Ｇ=(｛S｝，{a,b},P，Ｓ) P:Ｓ→aＳS→bSS→ε (2）右线性文法G=（｛S},{a，b},P,Ｓ）ﻩ P:S→ａSS→bSＳ→abｂ （3)此正则集为{bａ*｝ ﻩ右线性文法G=（{S，Ａ｝，{a,b},P,S）ﻩ P：S→bＡA→aAA→εﻩ(4)此正则集为{{a,b｝*aａ{a,b}*bｂ{a,b}*,{ａ，b}*bb{ａ,b｝*aa{a,ｂ}＊}ﻩﻩ右线性文法Ｇ=(｛S，A,Ｂ,Ｃ},{a,b},P,S) ﻩＰ:Ｓ→ａS/bＳ／aaA/bbＢA→aA/ｂA/bbCB→aB/ｂＢ/ａａCC→aＣ/bC／ε７.设正则集为a(ｂa)*构造右线性文法找出(1）中文法的有限自动机答:（1)右线性文法G＝({S,A｝,｛a，b},P,S) P:S→aＡA→bSＡ→εﻩ（2）自动机如下:P2P1ﻩaP2P1b（ｐ２是终结状态）９.相应图(a)(ｂ）的状态转换图写出正则式。(图略）由图可知q0＝ａｑ0+ｂq1+a+εq1=aｑ2+bq１ q0=ａq0＋bq1+ａ＝＞q1=aｂｑ1+bq1+ａaｑ0+ａa=（ｂ+ab)ｑ1+ａaq０＋ａａ=(b+aｂ)*(aaｑ０＋aa)=＞ｑ０=aｑ0＋b（b＋ａb)*(ａaq0+aa)+a+εﻩ=q０(a＋b(b＋ab）*aa）+b(b+ab)*ａa+a+ε=(a+ｂ(b+ab)*aa)*((b+ab)*aａ+a+ε)=(ａ＋ｂ(ｂ+aｂ)＊aa)*ｑ0=aq１+bq2+ａ+bｑ１＝aｑ0+bq2＋bq0=aｑ1+ｂq0+a=＞q1=aq0+baq1+bｂq０+bａ+b =(ba)*(ａq0+bbｑ0＋ba+ｂ)=>q2＝ａaq0+ａｂq2+bq0+ab+a＝(ab)*(aａq０+bq0+ab+a)=＞q0＝ａ(ba）*(a+ｂb）q0+ａ(ba)＊(ba＋ｂ)＋b(aｂ)*(ａa+b)q0＋b(ab）*（ab+a）+a+b =[a（ｂa）*（a+bb)+ｂ（ab)*(aａ+ｂ)］*(a(ba)*(bａ+ｂ)+b（ab)*(aｂ＋ａ)+a+b)10.设字母表T={a,b}，找出接受下列语言的DFＡ：具有3个连续b的所有字符串集合以aa为首的所有字符串集合以ａa结尾的所有字符串集合答:(1）M=({q0,q１ｑ2,ｑ3},{a,b},σ,q0,{q3}）,其中σ如下:abq0q０q1q1q0ｑ2q2q0ｑ3q3q3q3（2)Ｍ=({ｑ0,q1q2}，{ａ,b}，σ,q0，{ｑ2}),其中σ如下：abq０q１Φｑ1q2Φq2q2q2（3）M=({ｑ0，q1q２},｛a,ｂ},σ,q0，{q２｝),其中σ如下：abq０ｑ1ｑ0q１q2q0q2q2q014构造DＦＡM１等价于NＦAM,ＮFＡＭ如下:(1)M＝({q0,q１q２,q3},｛a,ｂ｝,σ,q0，{q3}),其中σ如下：ﻩσ(ｑ0,a）={q0，q１}σ(q0，b）=｛q0}ﻩσ(q1,a)={q２}σ(q1，b）={q２｝ σ（q2,ａ）=｛q3｝σ（q2,b)=Φﻩσ(q３,a)=｛q３}σ（q３,b)={q3}（２）M=({q0,q1ｑ2,ｑ３},{a,b｝,σ,ｑ０,{ｑ1，q2}),其中σ如下：ﻩσ(q0,a)={q1,q2}σ(q0,b)={q1}ﻩσ(q1,ａ)={ｑ2}σ(q1,b)={q1,q2}ﻩσ(q2,a)=｛q3}σ（q2,b）={ｑ0} σ(ｑ3,a)=Φσ(ｑ３,ｂ)＝{q0}答：(1)DFAM1＝{Q１,{a,b},σ１,[q0],｛［q０,q1,q3],[q0,q2，q3],［q０，q1,q2,ｑ3］}其中Q1＝{[q０］,［ｑ0，q１］,［ｑ０,q１,ｑ2］,［ｑ0,ｑ2],[q0,q1，q2,ｑ3],[ｑ0,q1，q3],［ｑ0，q2,ｑ3],[q0,q３]}σ1满足ab[q０］[q０,q1]［ｑ0]［q０，q1][ｑ0，q１,q2］[q0,ｑ2］[q０，q1，q2］［ｑ0,q1,q２,ｑ3］[ｑ0,q2]［q０,q2]［q０,ｑ１,q3]［ｑ０］[q0,q1,q2，q3][ｑ0，q1,q２，q3][q0，q2,ｑ３][q0,q1,q３][q0,ｑ1,ｑ2,q3］[ｑ0,ｑ2,q3][q0,q2,q3］[q0,q1,ｑ3]［q0，q3][q0,ｑ3]［q0,ｑ１,q３][q0,ｑ3](2）ＤFAM1＝{Q１,{ａ,ｂ｝,σ１,［q０],｛[q１],[q３],[q1，q3]，［q0,q1,q2],[q1,ｑ２],［q1,q2,q3］,［q2,q3］}其中Ｑ1＝｛[q0］,[q1,q3]，[ｑ1],［q2]，[q0,q1,ｑ２],[q1,ｑ２],［ｑ3],［q1,q2,q3],[q2，q3]}σ1满足ab［q0]［q1,q3][q１］[q１,ｑ3］[q2][ｑ0,ｑ１,q2][q１][q2][q1，q２][ｑ２][ｑ3］[ｑ０]［q0,q1,ｑ2][q1，q2,q３]［q0,q1,q2]［q1,ｑ2][q２,q3］[q０,q1，q２][q3]Φ[q０]［q1,q2,ｑ3］[ｑ2,q３][q0,q1,q2]［q2，q3][ｑ３]［q０]15.15.对下面矩阵表达的ε-NＦAεａbｃP(起始状态)φ｛p｝{q}{r｝ｑ{p}{q}{ｒ｝φr(终止状态）{q}｛r}φ{p｝给出该自动机接受的所有长度为3的串将此ε－ＮFA转换为没有ε的NFA答：（1）可被接受的的串共２3个,分别为aaｃ,aｂc,acc,bａc,ｂbc,bcｃ,ｃac，cｂc，ccｃ，caa,caｂ,cba，ｃbb,cca，cｃb,bba,aｃa,acb，bca,bcb,bａb,bbb,ａbb(2)ε-NFA：Ｍ=({p,q,r},{a,ｂ，c},σ,ｐ，r)其中σ如表格所示。由于ε-ｃlosure(p)=Φ则设不含ε的NFＡM1=（{ｐ,q,ｒ｝，{a,b,c}，σ1,p,r)σ1（ｐ，a)＝σ’（p,a)=ε-closｕre（σ(σ’（p,ε）,ａ）)=｛p}σ1(p,b)＝σ’(p,b)=ε-cｌoｓure(σ(σ’(ｐ,ε)，b))＝{p,ｑ}σ１(p,c)＝σ’（ｐ,c)＝ε－clｏｓｕre(σ（σ’(p,ε),c))＝｛p,ｑ,ｒ}σ1(q,a)=σ’（q,a)=ε-closure（σ（σ’(q,ε)，a))={p，ｑ}σ1（q，ｂ)=σ’(q,b）＝ε-clｏsure(σ(σ’(q,ε),b））={p，q，r}σ1(q，c)=σ’(ｑ，c）=ε-closure(σ（σ’(q,ε）,c))=｛p,q，r}σ1（r,a）=σ’(r,a)=ε-cｌoｓure(σ(σ’（r,ε),a))＝｛ｐ,q,r}σ１(r,b）=σ’(r，ｂ)=ε-clｏsuｒe(σ(σ’(r，ε),b))={p,q,ｒ}σ1(r,c）=σ’（r,c）=ε-closuｒｅ（σ(σ’(r,ε)，c))={p，q，r}图示如下：（ｒ为终止状态)pqｂ,cpqａ,b，ca，b,ca，b,ｃcａ,b,cｂ,ca，b,crra,b,c1６．设ＮFAM=({q0,ｑ1｝,{a，b},σ，q0，{q1}），其中σ如下:ﻩσ（q0，a)=｛q０，q1｝σ（q０,b)=｛q1｝ σ(q１,a）=Φσ(q１，ｂ)={q0,ｑ1}构造相应的DFAM1,并进行化简答：构造一个相应的ＤFAM1={Q１,{ａ,b},σ1，[q0]，｛[q1]，[ｑ0,q1]}其中Q１={[q0］,[ｑ1］,[ｑ0,q1］｝σ1满足ab[q0][ｑ0，q1][q1］［q1]Φ[q0,q1][q0,q1][q0,q１］[q0,q1]由于该DFＡ已是最简,故不用化简１7．使用泵浦引理,证明下列集合不是正则集:由文法G的生成式S→aSbＳ/ｃ产生的语言Ｌ(Ｇ){ω/ω∈｛a，b}＊且ω有相同个数的ａ和ｂ｝｛ａkcaｋ/k≥1}｛ωω/ω∈｛ａ,ｂ}*}证明:(1)在Ｌ(G)中,a的个数与b的个数相等假设L(Ｇ)是正则集，对于足够大的ｋ取ω=ａk(cb)kc令ω=ω1ω0ω2由于|ω0|＞0|ω1ω０｜≤k存在ω0使ω1ω0ｉω2∈L所以对于任意ω０只能取ω0=ａnn∈(0，k)则ω１ω0iω2=ak–ｎ（an)i(cb）kc在i不等于0时不属于L与假设矛盾。则L(G)不是正则集(2）假设该集合是正则集,对于足够大的k取ω=akbk令ω=ω1ω０ω2由于|ω０|>0｜ω1ω０|≤k存在ω0使ω1ω0iω２∈L所以对于任意ω０只能取ω0＝ａｎn∈(0,ｋ)则ω1ω0iω2＝ak–n（an)ibk在ｉ不等于０时a与b的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（3)假设该集合是正则集,对于足够大的k取ω＝akｃak令ω=ω1ω0ω2由于|ω0｜>0｜ω1ω０｜≤k存在ω0使ω1ω0iω2∈Ｌ所以对于任意ω0只能取ω0=aｎn∈(０，k)则ω1ω０iω2=ak–n(an)ｉcak在i不等于０时c前后ａ的个数不同，不属于该集合与假设矛盾。则该集合不是正则集(4)假设该集合是正则集，对于足够大的k取ωω=ａkbakb令ωω＝ω１ω0ω2由于|ω0|>0|ω1ω0｜≤k存在ω０使ω１ω０iω2∈L所以对于任意ω0只能取ω0＝ann∈(0,ｋ)则ω1ω0iω２=ak–ｎ(an)iｂaｋb在i不等于０时不满足ωω的形式,不属于该集合与假设矛盾。则该集合不是正则集18.构造米兰机和摩尔机对于{a,ｂ}*的字符串,假如输入以ｂaｂ结尾，则输出1；假如输入以bbａ结尾，则输出２；否则输出3。答:米兰机：ﻩ说明状态qaa表达成这个状态时,输入的字符串是以aa结尾。其他同理。ａ/3qaaqabqaaqabb/3a/３ａ／3b/3ｂ／1qbaqbbqbaqbbａ/2b/3 摩尔机，状态说明同米兰机。aaqaba,3b/3qaab,3b/3qaa,3b/3bａqaba,3b/3qaab,3b/3qaa,3b/3ａｂabqbab,1b/3qbb,3b/3qbba,2b/3qbab,1b/3qbb,3b/3qbba,2b/3abbb第四章把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法:S→A1｜A2，A1→Ａ3|A４，A2→A4｜Ａ5，A3→S|b|ε,A4→S|a，Ａ5→Ｓ|d|ε解:ﻩ⑴ﻩ由算法３，变换为无ε生成式：N’={S,A1,A2,A3,Ａ4,A５｝G1=(｛S1,Ｓ,A1,A2,A3,A４,A5},{a,b,d},P1，S1),其中生成式Ｐ１如下:Ｓ1→ε｜S,S→A1|A2,A1→Ａ３｜Ａ4,A２→A4|A５，Ａ3→Ｓ|b,A4→S|a,A５→S|ｄ，⑵ 由算法4，消单生成式：NＳ1＝{S１,Ｓ,A1,A2,A3,A4，Ａ５},NＳ=NA1=ＮA2=NＡ3=NA4=NA5＝{Ｓ,A1,Ａ２,A3，Ａ4,A5｝,运用算法4,则P1变为：Ｓ1→ａ|ｂ|ｄ|ε,S→a｜b|d,A1→a｜b|d,A2→a|b｜d，A3→a|ｂ|d,Ａ4→a｜ｂ|ｄ,Ａ5→a|ｂ|d⑶ 由算法1和算法2,消除无用符号，得到符合题目规定的等价文法:Ｇ１＝（｛S1}，{a,b,d},P1,Ｓ1)，其中生成式P1为：S１→a｜ｂ|d|ε.设2型文法G=({S,A,B，C,D,E,F},{ａ,ｂ,c},P，Ｓ),其中Ｐ：S→ASB|ε；A→ａＡS|a;Ｂ→SBS|A|bb试将Ｇ变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.解:ﻩ⑴ﻩ由算法3,变换为无ε生成式：Ｎ’=｛S}由Ｓ→ASＢ得出S→ASＢ|AB，由A→aAS得出A→aＡＳ｜aＡ,由Ｂ→SBＳ得出B→ＳBS｜SB｜BS|B,由S∈N’得出S１→ε|S,因此无ε的等效文法G1=({S1,Ｓ,A，B},｛ａ,b,d｝,P1，S1),其中生成式P1如下：S1→ε|S,Ｓ→ASB|ＡＢ，A→aAS|aA|a,B→ＳＢS|ＳB｜ＢS|B|Ａ｜bb,⑵ 由算法4，消单生成式：NS１={S1,S}，NS={Ｓ},NＡ={Ａ},NＢ={Ａ,B｝由于Ｓ→AＳＢ｜AB∈P且不是单生成式,故P１中有Ｓ1→ε｜ＡSＢ|AB,同理有S→ＡＳB|AB，A→aAS|aA|a,Ｂ→SＢS|SＢ|ＢS|aAＳ|aA|a|bb,因此生成的无单生成式等效文法为G1＝({S1,Ｓ，A，Ｂ｝,{a,b},P１，Ｓ1)，其中生成式P1如下：Ｓ1→ε|ASB|ＡB，Ｓ→ＡSＢ|AB,A→aAS|aＡ|a,B→SBS|SB|BS|aAＳ｜ａＡ|a|ｂb,⑶ﻩ由算法1和算法2,消除无用符号(此题没有无用符号);⑷ 转化为等价的Cｈｏmskｙ范式的文法:将S1→ASB变换为S→AC,Ｃ→SB,将S→ASＢ变换为S→AC,将A→aＡS｜aA变换为A→ED|EA,D→AS,Ｅ→ａ,将B→SBS|aＡS|aA|ａ|bb，变换为B→ＣS|EＤ|ＥA|ＦF,F→ｂ,⑸ 由此得出符合题目规定的等价文法：G１=({S1,Ｓ,A，B,C，D},{a,ｂ},P1,S1),其中生成式Ｐ1如下：S１→ε|AC｜AB,S→AC｜AB,Ａ→ED|EA|ａ，B→CＳ｜ＳB｜BS｜ＥD｜EＡ｜a|FF,C→ＳＢ，D→AS，Ｅ→a,F→b．将下列文法变换为等价的Ｇrｅibａch范式文法:⑴ﻩS→DD|a,D→ＳＳ|b解： 将非终结符排序为S,D,S为低位,Ｄ为高位, ⑴ﻩ对于Ｄ→SS,用S→ＤＤ|a代入得D→DDS|aS｜b,用引理4.２．4,变化为D→aS|b｜ａSD'|bD＇,Ｄ’→DＳ｜DＳD’，⑵ 将D生成式代入Ｓ生成式得S→ａＳD|ｂD｜aSＤ’D|bD'Ｄ｜ａ,⑶ﻩ将D生成式代入D’生成式得Ｄ’→aＳS|bＳ|aSD'Ｓ|bD'Ｓ|ａSSD＇|ｂSD'|aSD'SD＇|ｂD'ＳD',⑷ﻩ由此得出等价的Greiｂaｃｈ范式文法:G1＝({S,D,D’｝,{ａ，b}，P１,Ｓ),其中生成式P1如下:Ｓ→aＳＤ|bD｜ａSD’Ｄ｜bＤ'D|a,D→ａS|b｜aSＤ'|ｂD',Ｄ’→aSS|bS|aSＤ'S｜bD'S｜aＳSD'｜bＳD'|aSD'SＤ'|bD'ＳD'.ﻩ⑵ A1→A３b|A2a,Ａ2→Ａ1b|Ａ2A２a｜b，A３→A1ａ|Ａ3A3b｜a解:ﻩ⑴ﻩ转化为等价的Chomsky范式的文法:ﻩﻩＡ1→A3A4|A2A5,Ａ2→A1A4|Ａ2A６｜ｂ,A3→A１A5|A3A7|a，A4→b,A5→a,A6→A2A5,Ａ7→A3A4，⑵ﻩ转化为等价的Grｅibach范式的文法:将非终结符排序为Ａ１,Ａ2，Ａ3,A４,Ａ5，A1为低位Ａ5为高位,①对于A2→A１A4,用A1→A３Ａ4｜A2A5代入得A2→A3A4A4|A２Ａ５A4|Ａ2A6｜b,用引理4.2.4,变化为A2→A3A4Ａ4|b|A3A4Ａ４A2’｜ｂA2’，A2’→A5Ａ４A2’|Ａ6Ａ2’|Ａ５Ａ4|A6，②对于A３→A１Ａ５,用A1→A3A４|A2Ａ５代入得A3→Ａ3A4A5|Ａ2Ａ5A５|Ａ3A７｜a,A3生成式右边第一个字符仍是较低位的非终结符,将A２生成式代入A3生成式得A3→Ａ3A４Ａ5|A3A4A４A5A5|ｂA５A5|Ａ3Ａ４A４A２’A５A5｜ｂA2’Ａ５A5|A3A7|a,用引理4.2.4,变化为Ａ3→ｂＡ５A5|bＡ2’A5A5|a|bA5A5A3’｜ｂA2’A５A5A3’|aA3’,Ａ3’→A４A5|A４A４A5Ａ５|A4A4A２’A5A5｜A7|Ａ4A5A3’｜Ａ4A4A5A5Ａ3’｜A4Ａ4A2’A５Ａ5A3’|A7Ａ3’,③对于Ａ6→A２A5,将A２生成式代入A6生成式得Ａ6→A3A4A4A5|bA5|A3A4A4A2’A5|bA２’A５,A６生成式右边第一个字符仍是较低位的非终结符,将Ａ３生成式代入A6生成式得Ａ6→bA5A5A4Ａ4Ａ5|bA２’A５Ａ5Ａ4A４A５|ａA4Ａ４A５|bＡ5A5A3’Ａ4A4Ａ5|bA２’A5A5A3’A4A４A5|ａＡ3’A４A４A5|bＡ5A5Ａ4A4A2’A５|bA2’A5A5A４A4A２’A５|aA４A4Ａ2’Ａ5|bＡ5A５A3’A4A4A２’A５|ｂA2’Ａ5A5A3’Ａ4A４A２’Ａ5｜aA3’A4Ａ４A2’A5｜bA２’Ａ5|ｂA5,④对于A7→A3A4,将A3生成式代入Ａ7生成式得A７→bＡ5A5A4|bA2’A５Ａ5A4｜aA4|bＡ5A5A3’Ａ４|bA2’A5A5A３’A4|aA3’A4,⑤将A５，A6生成式代入A2’生成式得Ａ２’→aA4A2’｜bA５A５A4Ａ4A5A2’|bA2’A5A５A4A4Ａ5A2’|ａA4A4A5A２’｜bA5A５A3’A４A4A5A２’|bＡ2’Ａ5A5A3’A4A4A５A2’｜aＡ3’A4A４A5A２’|bA5A5A4A４A2’A5A２’|ｂA2’A５A5A４Ａ4Ａ2’Ａ5A2’|aＡ4A4A2’Ａ5A2’|bA5A５A3’A4A4Ａ2’A5A2’|bA2’A５Ａ５A３’A4Ａ4A2’A５A2’|aA3’A4Ａ4A2’A５A２’|ｂＡ2’A5Ａ2’｜bA５A２’|aＡ４|bA5Ａ5Ａ4A４A5|bＡ２’A5A5A4A4A５|aA４A4Ａ5｜bＡ5A5Ａ3’A4A4A５|ｂＡ２’A5A５A3’A4A4A5|aA3’A4A4Ａ５|bA5Ａ5A4A4A2’A5｜bA2’A5A５A4A４Ａ２’A5|aＡ4A4A２’A5|bA5Ａ5A3’A４Ａ4A2’A5|bA2’A5A５Ａ３’A4A4A2’A5｜ａA3’A4A４A２’A5｜bA2’A5|bA5,将Ａ4,A７生成式代入A3’生成式得Ａ3’→aA5|aA4A5Ａ５|ａＡ4A2’Ａ5A5|ａA５A3’|aA4A５A5A3’|ａA4A２’A5A5A3’|ｂA５A5A4|bA2’A5A5A4|ａA４|bA5Ａ5A3’A4｜bA2’Ａ５A5A3’A4|aA3’A4|bA5A5Ａ4A3’｜bA2’A5A5A4A3’|aA4Ａ3’|bＡ5A５A3’A４A３’|bA2’Ａ5Ａ5Ａ３’A4A3’|aＡ3’A4A3’，⑶ 由此得出等价的Gｒeibａch范式文法:G1=（{S,Ｄ,Ｄ’}，{a，ｂ}，Ｐ１,Ｓ),其中生成式Ｐ1如下：A1→A3A4｜A2Ａ５，A２→A3A4A４|b｜A３A４A4A２’|bA2’,A３→ｂA5A5|bA2’A5Ａ５｜a|bA5Ａ5A3’|bＡ２’A5A５A3’｜ａA３’,A４→b,Ａ5→a,Ａ6→bA５A５A４Ａ4A5｜bＡ2’A5Ａ5Ａ4A4A5｜aA4Ａ４A5|bA5A5A３’A4A4Ａ５|bA2’A5A5A3’A4A4A5|aA3’A4A4A5|bＡ５Ａ５A４A4A2’A５|ｂA２’Ａ5Ａ５A4Ａ4A２’A5|aA４A４A2’A5|ｂA5A5A３’Ａ４A4Ａ2’Ａ5|bA２’A５A5A3’A4A4A2’A5｜ａＡ3’A4A４Ａ2’A5|bA2’Ａ5|ｂA５,A7→bＡ5A5A４|bA2’A5A5A4|ａA4｜bA５A5Ａ３’A４|bA２’Ａ5A５A3’A4|aA３’Ａ４,A２’→ａＡ4Ａ2’|bA5A５A4A４A5A２’|bA2’Ａ5A5A4A４Ａ５A２’｜aＡ4A4A５A2’|bA5Ａ5A3’Ａ4A4Ａ5A２’|bA2’A5A5A3’A4A4A５A２’|ａA3’Ａ4Ａ4A5A2’｜bA5Ａ５A4Ａ4A2’A5A２’|bA2’A５A5A4A４A2’A5Ａ2’|aA4A4A2’A5A2’|bA５Ａ5Ａ3’A４A4Ａ2’A5A２’|bA2’A５A5A3’Ａ４A4Ａ２’Ａ５Ａ２’|ａＡ3’Ａ4A4A2’Ａ5A2’|bA2’A5Ａ2’|ｂA5A2’|aＡ４|bA5A5Ａ4A4A5|bA2’A5Ａ5A４A４Ａ5|aA4A４A5|bA５Ａ5Ａ3’Ａ4A４A５|bA２’A5A5A3’A4A4A5|aA3’A4A4A5｜bA５A5A4A4Ａ2’A5|bA2’A5Ａ5A4A4A2’Ａ5｜ａA4A4A２’Ａ５|ｂＡ５A５Ａ3’A４A4A2’A５|bA２’A５A5Ａ3’A4A4Ａ２’Ａ5|aＡ３’A４A4A2’A5｜bA2’A5|ｂA5,Ａ3’→aA5|ａA4A5Ａ5｜aA4A2’A5Ａ５|aA５A３’|aA4A5A5A3’|aA４A2’A5A５A3’|bA５A５A４|ｂA2’Ａ5A5A4|aA4|bA5A5A3’A4|bＡ2’A5A5Ａ3’A４|ａＡ３’A4|bＡ5A5Ａ４A3’|bA2’A5A５A４A3’|aＡ４Ａ3’｜ｂＡ5A5A3’A4A3’|bＡ2’A5A５Ａ３’Ａ4A3’|aA3’Ａ4A３’.设文法G有如下得生成式：S→aDD，D→aＳ|bS|a,构造等价的下推自动机．解: 根据Ｐ１62-１６3的算法,构造下推自动机M,使M按文法G的最左推导方式工作．ﻩ设M=(Q，T，Г,δ，q０,Ｚ0,F),其中Q={q0,qｆ}，T={ａ,b｝，Г＝{a,b,D，Ｓ},Ｚ0＝S，F={qf｝, δ定义如下：δ（ｑ０,ε,S)＝{(q０,aDD)},δ(ｑ0,ε，D)＝｛(q0,ａS),(q０，bＳ),(ｑ0,a)｝,δ(ｑ0，a,a)＝｛(ｑ0,ε)},δ(ｑ０，ε,ε)={(qf,ε）｝．给出产生语言Ｌ={aibｊck｜i,j,k≥０且i=ｊ或者j=k}的上下文无关文法.你给出的文法是否具有二义性?为什么?解:ﻩG=（｛S,A,B,C，D,Ｅ}，{a,ｂ,c}，P，S)P：Ｓ→AD|EB,A→aAｂ|ε,B→ｂBｃ|ε,D→cD|ε,E→aE|ε文法具有二义性。由于当句子ω中a，b,c个数相同时,对于ω存在两个不同的最左（右)推导。如abｃＬ，存在两个不同的最左推导SADaAbＤａbDabcCａbc及SEBaEBaBａbBcａbc。设下推自动机Ｍ=({q0,q１｝,{a,b},{Ｚ0,X}，δ，q0,Z0,φ),其中δ如下:δ（ｑ0,b,Z0）={（q0,XZ０)｝,δ(q0,ε,Z０)=｛(q0，ε）},Aδ（q０，ｂ，Ｘ)={(q0,XX)},δ(q1，b,Ｘ)={(q１,ε)},δ(q０，b,X)={(q１,X)},δ(q１,a，Z0)=｛（ｑ０,Ｚ０）},试构造文法G产生的语言Ｌ（G)=Ｌ(M).解:ﻩ在G中,N＝{[q0,Z0,ｑ0],[q0,Z0,q1］,[q０，Ｘ,ｑ0],[q０,X,q1］,［q1,Z0,q０],[q1，Z0，q1]，[q１，X,q0］，[q1,Ｘ，ｑ１]}． ⑴ﻩＳ生成式有S→[q0,Z0,ｑ0],S→［ｑ0,Ｚ0,q1］,ﻩ根据δ（ｑ０,ｂ，Z0)={(ｑ0,ＸＺ０)}，则有[q0，Ｚ０,q0］→b[q0,Ｘ,q0]［q０,Ｚ0,q0］,[q0,Z0，q０]→b［q0,X，q1］[q１,Z0,ｑ0]，[ｑ0,Z０，q1]→b[ｑ0，Ｘ,q0][ｑ0，Ｚ0，q1］,[q０,Ｚ0,ｑ１]→b[q0，Ｘ,q１][q1,Z0，q1］， 由于有δ(ｑ0,ｂ,X)={（q0,XX)},则有［q0,X,q0］→b［q0,X,ｑ0][q０,X，q0],[q0,Ｘ,q0］→b[q0，Ｘ，q1］[q1，X,ｑ０],[q０,X,q1]→b［q0,X,q0][ｑ0,X,q１]，[q0，X，q１]→ｂ[q0,X,q１][q１,X，ｑ1]，ﻩ由于有δ(q0,ａ，X)={(q1,Ｘ）},则有[q０，X，ｑ0]→a［ｑ1，X,q０]，[q0，X,q１]→a[q１,X,q１]， 由于有δ(q1，a,Ｚ0)=｛(q０,Z0)｝，则有[q１,Z０,ｑ0］→ａ[q0,Z０，q0],[ｑ1,Z0,q1］→a[q0,Z0，ｑ1],由于有δ(q０,ε,Z0)=｛(q0,ε)},则有［q０,Z0,q0]→ε， 由于有δ(q1,b,X）={(q1,ε)｝,则有[q1,X，q１］→ε ⑵ﻩ运用算法1和算法２,消除无用符号后，得出文法G产生的语言L（G)＝{Ｎ,T，P,S} 其中N={S,[ｑ0，Z0,q0]，[ｑ1,Ｚ0，ｑ0],[q1，X，ｑ1],［q0,X，q1]},T={a，b},生成式P如下:Ｓ→[ｑ0,Ｚ0,q0]，[q0,Ｚ0，q0]→ｂ［ｑ0,X,q1][q１,Z0,ｑ0],[q0，Ｘ,ｑ１]→b[q０,X,q1][ｑ1,Ｘ,q１］,[q0,X，ｑ1］→a[q1,X,q1］,[q1,Z0,q0]→a［q0，Z０,q0］,[q０,Z0，q0］→ε,[q0,Ｚ0,q0]→ε.证明下列语言不是上下文无关语言:⑴ﻩ{ａnｂncm|ｍ≤ｎ｝；证明:ﻩ假设L是上下文无关语言,由泵浦引理,取常数ｐ,当ω∈L且｜ω|≥p时，可取ω=apbpcp,将ω写为ω＝ω１ω2ω0ω3ω4,同时满足|ω2ω0ω3|≤p⑴ﻩω2和ω3不也许同时分别包含a和c,由于在这种情况下,有|ω２ω0ω3｜>p；⑵ﻩ假如ω２和ω3都只包含a(ｂ),即ω２ω0ω３=aj(bj)（ｊ≤ｐ),则当i≠1时,ω１ω2iω０ω３iω4中会出现a的个数与b的个数不等;假如ω2和ω３都只包含c,即ω2ω0ω3＝cｊ（j≤p)，当i大于1时，ω1ω２iω0ω3iω４中会出现ｃ的个数大于a的个数（b的个数);⑶ 假如ω2和ω3分别包含a和b(ｂ和ｃ)，当ｉ=0时ω1ω2ｉω0ω３iω4中会出现ａ,ｂ的个数小于c的个数（或a,ｂ个数不等)这些与假设矛盾，故L不是上下文无关语言.⑵ﻩ{aｋ|k是质数};证明: 假设L是上下文无关语言，由泵浦引理,取常数p,当ω∈L且|ω｜≥p时,可取ω=ak（k≥p且k≠1)，将ω写为ω=ω１ω2ω0ω3ω４,同时满足｜ω2ω0ω3｜≤p,且｜ω2ω３｜=ｊ≥1,则当i＝ｋ+1时，|ω1ω2ｉω0ω3iω4|=k＋（i-1)*j＝k+ｋ*j=k*（１+ｊ），k*(1+j)至少包含因子k且ｋ≠１,因此必然不是质数,即ω1ω2iω0ω３iω4不属于L. 这与假设矛盾，故L不是上下文无关语言．⑶ 由ａ,b,c组成的字符串且是具有a,b,c的个数相同的所有字符串.证明: 假设Ｌ是上下文无关语言,由泵浦引理,取常数p，当ω∈Ｌ且|ω|≥p时,可取ω=aｋbkck（k≥p)，将ω写为ω＝ω1ω２ω0ω3ω4，同时满足｜ω2ω0ω3｜≤p⑴ﻩω2和ω3不也许同时分别包含a和c,由于在这种情况下,有|ω2ω0ω３|＞p;⑵ 假如ω２和ω3都只包含a(ｂ或ｃ），即ω２ω0ω３=ａｊ(bj或cj)(ｊ≤p),则当i≠1时,ω1ω2iω０ω3iω4中会出现a，b,ｃ的个数不再相等；⑶ 假如ω2和ω3分别包含a和b(b和c）,ω1ω２iω０ω3ｉω4中会出现a,ｂ的个数与c的不等;这些与假设矛盾，故L不是上下文无关语言.设G是Cｈｏmsky范式文法,存在ω∈Ｌ(Ｇ)，求在边沿为ω的推导树中,最长的途径长度与ω的长度之间的关系.解:ﻩ设边沿为ω的推导树中,最长途径长度为ｎ,则它与ω的长度之间的关系为|ω｜≤２ｎ-1.由于由Chomsｋy范式