2023年北京郵電大學自動機課后習題答案

形式語言與自動機第二章4.找出右線性文法，能構(gòu)成長度為1至5個字符且以字母為首的字符串。答：G={Ｎ,T,Ｐ，S}?其中N={Ｓ,Ａ，B,C，D}Ｔ={ｘ,ｙ｝其中x∈{所有字母}y∈{所有的字符｝P如下: S→xS→xＡA→yA→yBB→yB→yCＣ→yＣ→yDＤ→ｙ6．構(gòu)造上下文無關(guān)文法可以產(chǎn)生Ｌ={ω/ω∈{a,b}＊且ω中ａ的個數(shù)是ｂ的兩倍｝答: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７．找出由下列各組生成式產(chǎn)生的語言（起始符為S)Ｓ→SaSS→bS→aSbS→cS→aS→aEE→aS答：（１)b(aｂ）ｎ/n≥0}或者Ｌ=｛(ba)nb/ｎ≥0}(２)L＝｛ancbn/n≥０}（3)Ｌ={ａ2n＋１/ｎ≥０}第三章下列集合是否為正則集,若是正則集寫出其正則式。具有偶數(shù)個a和奇數(shù)個b的{a,b}＊上的字符串集合具有相同個數(shù)a和b的字符串集合不含子串a(chǎn)ｂ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(chǎn)ｂａ的{a,b｝*上的字符串集合?顯然這是正則集，可以寫出表達式和畫出自動機。（略)?則不包含子串a(chǎn)ｂa的{ａ，b}*上的字符串集合L是L’的非。根據(jù)正則集的性質(zhì),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.為下列正則集,構(gòu)造右線性文法：(1）{ａ,b}＊(２)以aｂb結(jié)尾的由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／ε７.設(shè)正則集為a(ｂa)*構(gòu)造右線性文法找出(1）中文法的有限自動機答:（1)右線性文法G＝({S,A｝,｛a，b},P,S) P:S→aＡA→bSＡ→ε?（2）自動機如下:P2P1?aP2P1b（ｐ２是終結(jié)狀態(tài)）９.相應圖(a)(ｂ）的狀態(tài)轉(zhuǎn)換圖寫出正則式。(圖略）由圖可知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.設(shè)字母表T={a,b}，找出接受下列語言的DFＡ：具有3個連續(xù)b的所有字符串集合以aa為首的所有字符串集合以ａa結(jié)尾的所有字符串集合答:(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構(gòu)造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(起始狀態(tài))φ｛p｝{q}{r｝ｑ{p}{q}{ｒ｝φr(終止狀態(tài)）{q}｛r}φ{(diào)p｝給出該自動機接受的所有長度為3的串將此ε－ＮFA轉(zhuǎn)換為沒有ε的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)=Φ則設(shè)不含ε的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}圖示如下：（ｒ為終止狀態(tài))pqｂ,cpqａ,b，ca，b,ca，b,ｃcａ,b,cｂ,ca，b,crra,b,c1６．設(shè)ＮFAM=({q0,ｑ1｝,{a，b},σ，q0，{q1}），其中σ如下:?σ（q0，a)=｛q０，q1｝σ（q０,b)=｛q1｝ σ(q１,a）=Φσ(q１，ｂ)={q0,ｑ1}構(gòu)造相應的DFAM1,并進行化簡答：構(gòu)造一個相應的Ｄ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Ｓ/ｃ產(chǎn)生的語言Ｌ(Ｇ){ω/ω∈｛a，b}＊且ω有相同個數(shù)的ａ和ｂ｝｛ａkcaｋ/k≥1}｛ωω/ω∈｛ａ,ｂ}*}證明:(1)在Ｌ(G)中,a的個數(shù)與b的個數(shù)相等假設(shè)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與假設(shè)矛盾。則L(G)不是正則集(2）假設(shè)該集合是正則集,對于足夠大的k取ω=akbk令ω=ω1ω０ω2由于|ω０|>0｜ω1ω０|≤k存在ω0使ω1ω0iω２∈L所以對于任意ω０只能取ω0＝ａｎn∈(0,ｋ)則ω1ω0iω2＝ak–n（an)ibk在ｉ不等于０時a與b的個數(shù)不同，不屬于該集合與假設(shè)矛盾。則該集合不是正則集（3)假設(shè)該集合是正則集,對于足夠大的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前后ａ的個數(shù)不同，不屬于該集合與假設(shè)矛盾。則該集合不是正則集(4)假設(shè)該集合是正則集，對于足夠大的k取ωω=ａkbakb令ωω＝ω１ω0ω2由于|ω0|>0|ω1ω0｜≤k存在ω０使ω１ω０iω2∈L所以對于任意ω0只能取ω0＝ann∈(0,ｋ)則ω1ω0iω２=ak–ｎ(an)iｂaｋb在i不等于０時不滿足ωω的形式,不屬于該集合與假設(shè)矛盾。則該集合不是正則集18.構(gòu)造米蘭機和摩爾機對于{a,ｂ}*的字符串,假如輸入以ｂaｂ結(jié)尾，則輸出1；假如輸入以bbａ結(jié)尾，則輸出２；否則輸出3。答:米蘭機：?說明狀態(tài)qaa表達成這個狀態(tài)時,輸入的字符串是以aa結(jié)尾。其他同理。ａ/3qaaqabqaaqabb/3a/３ａ／3b/3ｂ／1qbaqbbqbaqbbａ/2b/3 摩爾機，狀態(tài)說明同米蘭機。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變?yōu)椋海?→ａ|ｂ|ｄ|ε,S→a｜b|d,A1→a｜b|d,A2→a|b｜d，A3→a|ｂ|d,Ａ4→a｜ｂ|ｄ,Ａ5→a|ｂ|d⑶ 由算法1和算法2,消除無用符號，得到符合題目規(guī)定的等價文法:Ｇ１＝（｛S1}，{a,b,d},P1,Ｓ1)，其中生成式P1為：S１→a｜ｂ|d|ε.設(shè)2型文法G=({S,A,B，C,D,E,F},{ａ,ｂ,c},P，Ｓ),其中Ｐ：S→ASB|ε；A→ａＡS|a;Ｂ→SBS|A|bb試將Ｇ變換為無ε生成式,無單生成式,沒有無用符號的文法,再將其轉(zhuǎn)換為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,消除無用符號(此題沒有無用符號);⑷ 轉(zhuǎn)化為等價的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→ｂ,⑸ 由此得出符合題目規(guī)定的等價文法：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解： 將非終結(jié)符排序為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解:?⑴?轉(zhuǎn)化為等價的Chomsky范式的文法:??Ａ1→A3A4|A2A5,Ａ2→A1A4|Ａ2A６｜ｂ,A3→A１A5|A3A7|a，A4→b,A5→a,A6→A2A5,Ａ7→A3A4，⑵?轉(zhuǎn)化為等價的Grｅibach范式的文法:將非終結(jié)符排序為Ａ１,Ａ2，Ａ3,A４,Ａ5，A1為低位Ａ5為高位,①對于A2→A１A4,用A1→A３Ａ4｜A2A5代入得A2→A3A4A4|A２Ａ５A(chǔ)4|Ａ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生成式右邊第一個字符仍是較低位的非終結(jié)符,將A２生成式代入A3生成式得A3→Ａ3A４Ａ5|A3A4A４A5A5|ｂA５A(chǔ)5|Ａ3Ａ４A４A２’A５A(chǔ)5｜ｂA2’Ａ５A(chǔ)5|A3A7|a,用引理4.2.4,變化為Ａ3→ｂＡ５A(chǔ)5|bＡ2’A5A5|a|bA5A5A3’｜ｂA2’A５A(chǔ)5A3’|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６生成式右邊第一個字符仍是較低位的非終結(jié)符,將Ａ３生成式代入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５A(chǔ)3’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(chǔ)５A(chǔ)4Ａ4A5A2’|bA2’A5A５A(chǔ)4A4Ａ5A2’|ａA4A4A5A２’｜bA5A５A(chǔ)3’A４A4A5A２’|bＡ2’Ａ5A5A3’A4A4A５A(chǔ)2’｜aＡ3’A4A４A5A２’|bA5A5A4A４A2’A5A２’|ｂA2’A５A(chǔ)5A４Ａ4Ａ2’Ａ5A2’|aＡ4A4A2’Ａ5A2’|bA5A５A(chǔ)3’A4A4Ａ2’A5A2’|bA2’A５Ａ５A(chǔ)３’A4Ａ4A2’A５A(chǔ)2’|aA3’A4Ａ4A2’A５A(chǔ)２’|ｂＡ2’A5Ａ2’｜bA５A(chǔ)２’|aＡ４|bA5Ａ5Ａ4A４A5|bＡ２’A5A5A4A4A５|aA４A4Ａ5｜bＡ5A5Ａ3’A4A4A５|ｂＡ２’A5A５A(chǔ)3’A4A4A5|aA3’A4A4Ａ５|bA5Ａ5A4A4A2’A5｜bA2’A5A５A(chǔ)4A４Ａ２’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５A(chǔ)3’|aA4A５A(chǔ)5A3’|ａA4A２’A5A5A3’|ｂA５A(chǔ)5A4|bA2’A5A5A4|ａA４|bA5Ａ5A3’A4｜bA2’Ａ５A(chǔ)5A3’A4|aA3’A4|bA5A5Ａ4A3’｜bA2’A5A5A4A3’|aA4Ａ3’|bＡ5A５A(chǔ)3’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５A(chǔ)3’｜ａA３’,A４→b,Ａ5→a,Ａ6→bA５A(chǔ)５A(chǔ)４Ａ4A5｜bＡ2’A5Ａ5Ａ4A4A5｜aA4Ａ４A5|bA5A5A３’A4A4Ａ５|bA2’A5A5A3’A4A4A5|aA3’A4A4A5|bＡ５Ａ５A(chǔ)４A4A2’A５|ｂA２’Ａ5Ａ５A(chǔ)4Ａ4A２’A5|aA４A４A2’A5|ｂA5A5A３’Ａ４A4Ａ2’Ａ5|bA２’A５A(chǔ)5A3’A4A4A2’A5｜ａＡ3’A4A４Ａ2’A5|bA2’Ａ5|ｂA５,A7→bＡ5A5A４|bA2’A5A5A4|ａA4｜bA５A(chǔ)5Ａ３’A４|bA２’Ａ5A５A(chǔ)3’A4|aA３’Ａ４,A２’→ａＡ4Ａ2’|bA5A５A(chǔ)4A４A5A２’|bA2’Ａ5A5A4A４Ａ５A(chǔ)２’｜aＡ4A4A５A(chǔ)2’|bA5Ａ5A3’Ａ4A4Ａ5A２’|bA2’A5A5A3’A4A4A５A(chǔ)２’|ａA3’Ａ4Ａ4A5A2’｜bA5Ａ５A(chǔ)4Ａ4A2’A5A２’|bA2’A５A(chǔ)5A4A４A2’A5Ａ2’|aA4A4A2’A5A2’|bA５Ａ5Ａ3’A４A4Ａ2’A5A２’|bA2’A５A(chǔ)5A3’Ａ４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５A(chǔ)5A4A4Ａ2’A5|bA2’A5Ａ5A4A4A2’Ａ5｜ａA4A4A２’Ａ５|ｂＡ５A(chǔ)５Ａ3’A４A4A2’A５|bA２’A５A(chǔ)5Ａ3’A4A4Ａ２’Ａ5|aＡ３’A４A4A2’A5｜bA2’A5|ｂA5,Ａ3’→aA5|ａA4A5Ａ5｜aA4A2’A5Ａ５|aA５A(chǔ)３’|aA4A5A5A3’|aA４A2’A5A５A(chǔ)3’|bA５A(chǔ)５A(chǔ)４|ｂA2’Ａ5A5A4|aA4|bA5A5A3’A4|bＡ2’A5A5Ａ3’A４|ａＡ３’A4|bＡ5A5Ａ４A3’|bA2’A5A５A(chǔ)４A3’|aＡ４Ａ3’｜ｂＡ5A5A3’A4A3’|bＡ2’A5A５Ａ３’Ａ4A3’|aA3’Ａ4A３’.設(shè)文法G有如下得生成式：S→aDD，D→aＳ|bS|a,構(gòu)造等價的下推自動機．解: 根據(jù)Ｐ１62-１６3的算法,構(gòu)造下推自動機M,使M按文法G的最左推導方式工作．?設(shè)M=(Q，T，Г,δ，q０,Ｚ0,F),其中Q={q0,qｆ}，T={ａ,b｝，Г＝{a,b,D，Ｓ},Ｚ0＝S，F(xiàn)={qf｝, δ定義如下：δ（ｑ０,ε,S)＝{(q０,aDD)},δ(ｑ0,ε，D)＝｛(q0,ａS),(q０，bＳ),(ｑ0,a)｝,δ(ｑ0，a,a)＝｛(ｑ0,ε)},δ(ｑ０，ε,ε)={(qf,ε）｝．給出產(chǎn)生語言Ｌ={aibｊck｜i,j,k≥０且i=ｊ或者j=k}的上下文無關(guān)文法.你給出的文法是否具有二義性?為什么?解:?G=（｛S,A,B,C，D,Ｅ}，{a,ｂ,c}，P，S)P：Ｓ→AD|EB,A→aAｂ|ε,B→ｂBｃ|ε,D→cD|ε,E→aE|ε文法具有二義性。由于當句子ω中a，b,c個數(shù)相同時,對于ω存在兩個不同的最左（右)推導。如abｃＬ，存在兩個不同的最左推導SADaAbＤａbDabcCａbc及SEBaEBaBａbBcａbc。設(shè)下推自動機Ｍ=({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òu)造文法G產(chǎn)生的語言Ｌ（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］,?根據(jù)δ（ｑ０,ｂ，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產(chǎn)生的語言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]→ε.證明下列語言不是上下文無關(guān)語言:⑴?{ａnｂncm|ｍ≤ｎ｝；證明:?假設(shè)L是上下文無關(guān)語言,由泵浦引理,取常數(shù)ｐ,當ω∈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中會出現(xiàn)a的個數(shù)與b的個數(shù)不等;假如ω2和ω３都只包含c,即ω2ω0ω3＝cｊ（j≤p)，當i大于1時，ω1ω２iω0ω3iω４中會出現(xiàn)ｃ的個數(shù)大于a的個數(shù)（b的個數(shù));⑶ 假如ω2和ω3分別包含a和b(ｂ和ｃ)，當ｉ=0時ω1ω2ｉω0ω３iω4中會出現(xiàn)ａ,ｂ的個數(shù)小于c的個數(shù)（或a,ｂ個數(shù)不等)這些與假設(shè)矛盾，故L不是上下文無關(guān)語言.⑵?{aｋ|k是質(zhì)數(shù)};證明: 假設(shè)L是上下文無關(guān)語言，由泵浦引理,取常數(shù)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且ｋ≠１,因此必然不是質(zhì)數(shù),即ω1ω2iω0ω３iω4不屬于L. 這與假設(shè)矛盾，故L不是上下文無關(guān)語言．⑶ 由ａ,b,c組成的字符串且是具有a,b,c的個數(shù)相同的所有字符串.證明: 假設(shè)Ｌ是上下文無關(guān)語言,由泵浦引理,取常數(shù)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中會出現(xiàn)a，b,ｃ的個數(shù)不再相等；⑶ 假如ω2和ω3分別包含a和b(b和c）,ω1ω２iω０ω3ｉω4中會出現(xiàn)a,ｂ的個數(shù)與c的不等;這些與假設(shè)矛盾，故L不是上下文無關(guān)語言.設(shè)G是Cｈｏmsky范式文法,存在ω∈Ｌ(Ｇ)，求在邊沿為ω的推導樹中,最長的途徑長度與ω的長度之間的關(guān)系.解:?設(shè)邊沿為ω的推導樹中,最長途徑長度為ｎ,則它與ω的長度之間的關(guān)系為|ω｜≤２ｎ-1.由于由Chomsｋy范式