北京郵電大學-形式語言與自動機-課后習題答案

形式語言與自動機第二章4.找出右線性文法，能構成長度為1至5個字符且以字母為首的字符串。答：G={N,T,P,S)其中N={S,A,B,C,D}T={x,y}其中xC{所有字母}yC{所有的字符}P如下:—xS-xAA-yA-yBB-yB-yCC-yC-yDD-y.構造上下文無關文法能夠產生L={①/aC{a,b}*且3中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-Sbaa.找出由下列各組生成式產生的語言(起始符為S)⑴S—SaSS—bS-aSbS—aS-aEE-aS答：(1)b(ab)n/n>0}或者L={(ba)nb/n>0}L={ancbn/n>0}(3)L={a2n+1/n>0}第三章.下列集合是否為正則集，若是正則集寫出其正則式。含有偶數個a和奇數個b的{a,b}*上的字符串集合含有相同個數a和b的字符串集合不含子串aba的{a,b}*上的字符串集合答：(1)是正則集，自動機如下(2)不是正則集，用泵浦引理可以證明，具體見17題(2)(3)是正則集先看L'為包含子串aba的{a,b}*上的字符串集合顯然這是正則集，可以寫出表達式和畫出自動機。(略)則不包含子串aba的{a,b}*上的字符串集合L是L'的非。根據正則集的性質，L也是正則集。.對下列文法的生成式，找出其正則式G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S—aAS—BA—abSA—bBB—bB—cCC—DD—bBD—dG=({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+e)(cb)*(cd+b)(2)由生成式得：S=aA+B①A=bB+cC②B=a+bB③C=D+abB④D=c?由③得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*a.為下列正則集，構造右線性文法：⑴{a,b}*⑵以abb結尾白^由a和b組成的所有字符串的集合(3)以b為首后跟若干個a的字符串的集合(4)含有兩個相繼a和兩個相繼b的由a和b組成的所有字符串集合答：(1)右線性文法G=({S},{a,b},P,S)P:S—aSSH>bSS—e(2)右線性文法G=({S},{a,b},P,S)P:S—aSS-^bSS—abb(3)此正則集為{ba*}右線性文法G=({S,A},{a,b},P,S)P:SfbAA-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:SfaAA-bSA一e(2)自動機如下：(p2是終結狀態(tài))9.對應圖(a)(b)的狀態(tài)轉換圖寫出正則式。(圖略)(1)由圖可知qo=aqo+bq1+a+￡q〔=aq2+bq1qo=aqo+bq1+a=>q1=abq1+bq1+aaqo+aa=(b+ab)q1+aaqo+aa=(b+ab)*(aaqo+aa)=>qo=aqo+b(b+ab)*(aaqo+aa)+a+&=qo(a+b(b+ab)*aa)+b(b+ab)*aa+a+e=(a+b(b+ab)*aa)*((b+ab)*aa+a+e)=(a+b(b+ab)*aa)*qo=aq1+bq2+a+bq1=aqo+bq2+bqo=aq1+bqo+a=>q1=aqo+baq1+bbqo+ba+b=(ba)*(aqo+bbqo+ba+b)=>q2=aaqo+abq2+bqo+ab+a=(ab)*(aaqo+bqo+ab+a)

=>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)字母表T={a,b},找出接受下列語言的DFA:含有3個連續(xù)b的所有字符串集合以aa為首的所有字符串集合以aa結尾的所有字符串集合14構造DFAMi等價于NFAM,NFAM如下：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}⑵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)={q。}答：(1)DFAM1={Q1,{a,b},C,[q0],{[q0,q1,q3],[q0,q2,q3],[q0,q1,q2,q3]}其中Q1={[q0],[q0,q1],[q0,q1,q2],[q0,q2],[q0,q[，q2,q3],[q0,q1,q3],[q0,q2,q3],[q0,q3]}C滿足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,qi,q2,q3][q0,qi,q2,q3][q0,q2,q3][q0,qi,q3][q0,qi,q2,q3][q0,q2,q3][q0,q2,q3][q0,q1,q3][q0,q3][q0,q3][q0,q1,q3][q0,q3]⑵DFAMi={Qi,{a,b}J1,[q0],{[qi],[q*[qi,q3],[q0,qi,q2],[qi,q2],[qi,q2,q3],[q2,q3]}其中Qi={[q0],[qi,q3],[qi],[q2],[q0,qi,q2],[qi,q2],[q3],[qi,q2,q3],[q2,q3]}i滿足ab[q0][qi,q3][q1][q1,q3][q2][q0,qi,q2][qi][q2][qi,q2][q2][q3]r[q0][q0,qi,q2][qi,q2,q3][q0,qi,q2][qi,q2][q2,q3][q0,qi,q2][q3]①[q。][qi,q2,q3][q2,q3][q0,qi,q2][q2,q3][q3][q0]i5.i5.對下面矩陣表示的￡-NFA￡abcp（起始狀態(tài)）{p}]{q}{r}q{p}{q}{r}r（終止狀態(tài)）{q}{r}「6.{p}(i)給出該自動機接收的所有長度為3的串(2)將此e-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￡-NFA:M=({p,q,r},{a,b,c},"p,r)其中工如表格所示。因為e-closure(p)=①則設不含e的NFAM=({p,q,r},{a,b,c},i,p,r)(i(p,a)=L(p,a)=:e-closure(工(t；'(p,￡),a))={p}乙i(p,b)=L(p,b)二=e-closure(工（工：'(p,e),b))={p,q}乙i(p,c)=乙'(p,c)=；e-closure(工((「(p,￡),c))={p,q,r}乙i(q,a)=L(q,a)=:e-closure(工((,'(q,e),a))={p,q}乙i(q,b)=乙'(q,b)=:e-closure(工(tJ(q,e),b))={p,q,r}乙i(q,c)=乙’(q,c)=e-closure(工，(q,￡),c))={p,q,r}乙i(r,a)=:L(r,a)=e-closure(工（工\r,￡),a))={p,q,r}L(r,b)=L(r,b)=e-closure(工（工'(r,￡),b))={p,q,r}乙i(r,c)=(二'(r,c)=e-closure(；C(工'(r,￡),c))={p,q,r}圖示如下：（r為終止狀態(tài)）b,c

a,b,ca,b,ca,b,ca,b,c.設NFAM=({q0,qi},{a,b},"q0,{qi}),其中(如下：工(qo,a戶{qo,qi}((qo,b)={q1}(q1,a)=①(qi,b)={q0,q1}構造相應的DFAMi,并進行化簡答：構造一個相應的DFAMi={Qi,{a,b}Ji,[qo],{[qi],[qo,qi]}其中Qi={[q。],[qi],[qo,qi]}C滿足ab[q0][q0,qi][qi][q1]①[q0,qi][q0,qi][q0,qi][q0,qi]由于該DFA已是最簡，故不用化簡.使用泵浦引理，證明下列集合不是正則集：由文法G的生成式S-aSbS/c產生的語言L(G){3/3C{a,b}*且3有相同個數的a和b}{akcak/k>i}{33/3C{a,b}*}證明：(i)在L(G)中，a的個數與b的個數相等假設L(G)是正則集，對于足夠大的k取3=ak(cb)kc令3=3i3032因為|30|>0|3i3o|<k存在30使3i30iCO2€L所以對于任意3o只能取3o=annC(0,k)則39屋2=akn(an)i(cb)kc在i不等于0時不屬于L與假設矛盾。則L(G)不是正則集(2)假設該集合是正則集，對于足夠大的k取3=akbk令3=39032因為|30|>0|3〔30|<k存在30使COiCO032CL所以對于任意30只能取30=annC(0,k)則3i30i32=akn(an)ibk在i不等于0時a與b的個數不同，不屬于該集合與假設矛盾。則該集合不是正則集(3)假設該集合是正則集，對于足夠大的k取3=akcak令3=39032因為|3。|>0|3i30|<k存在30使3i3032CL所以對于任意30只能取30=annC(0,k)則3130i32=akn(a所以對于任意30只能取30=annC(0,k)則3130i32=akn(an)icak在i不等于0時c前后a的個數不同，不屬于該集合與假設矛盾。則該集合不是正則集(4)假設該集合是正則集，對于足夠大的令33=313032因為|30|>0|3130|<k存在30使3130所以對于任意30只能取30=ann6(0,k)k?、?=akbakb則390i32=akn(an)ibakb在i與假設矛盾。則該集合不是正則集不等于0時不滿足33的形式，不屬于該集合18.構造米蘭機和摩爾機對于{a,b}*的字符串，如果輸入以出2；否則輸出3。答：米蘭機：說明1犬態(tài)qaa表示到這個狀態(tài)時,bab結尾，則輸出1;如果輸入以bba結尾，則輸aa結尾。其他同理。輸入的字符串是以b/3摩爾機，狀態(tài)說明同米蘭機。bb第四章.把下列文法變換為無￡生成式、無單生成式和沒有無用符號的等價文法:S|b|￡,A4一S|a,A5一S|dS一A1|A2,A1一A3|A4,AS|b|￡,A4一S|a,A5一S|d1解：⑴由算法3,變換為無￡生成式：N'={S,Al,A2,A3,A4,A5}G1=({S1,S,Al,A2,A3,A4,A5},{a,b,d},P1,Si)，其中生成式Pi如下：Si—￡|S,S-AllA2,Ai—A3|A4,A2-A4|A5,A3—Slb,A4—S|a,A5—S|d,⑵由算法4,消單生成式：NS1={Sl,S,Al,A2,A3,A4,A5},Ns=NA1=NA2=NA3=NA4=NA5={S,A1,A2,A3,A4,A5},運用算法4,則P1變?yōu)椋篠1-a|b|d|￡,S—a|b|d,A1-a|b|d,A2-a|b|d,A3-a|b|d,A4-a|b|d,A5—a|b|d⑶由算法1和算法2,消除無用符號，得到符合題目要求的等價文法：G1=({S1},{a,b,d},P1,S1)，其中生成式PE:S1-a|b|d|￡..設2型文法G=({S,A,B,C,D,E,F},{a,b,c},P,S)，其中P:S—ASB|￡;A—aAS|a;B—SBS|A|bb試將G變換為無￡生成式，無單生成式，沒有無用符號的文法，再將其轉換為Chomsky范式.解：⑴由算法3,變換為無￡生成式：N'={S}由S—ASB得出S—ASB|AB,由A—aAS得出A—aAS|aA,由B—SBS得出B—SBS|SB|BS|B,由SCN'得出S1-&|S,因此無￡的等效文法G1=({S1,S,A,B},{a,b,d},P1,&)，其中生成式P1如下:Si—￡|S,S—ASB|AB,A—aAS|aA|a,B—SBS|SB|BS|B|A|bb,⑵由算法4,消單生成式：Ns1={S1,S},Ns={S},Na={A},Nb={A,B}由于S-ASB|ABCP且不是單生成式，故P1中有Sife|ASB|AB,同理有S—ASB|AB,A—aAS|aA|a,B—SBS|SB|BS|aAS|aA|a|bb,因此生成的無單生成式等效文法為Gi=({Si,S,A,B},{a,b},Pi,Si)，其中生成式Pi如下：Si—&|ASB|AB,S—ASB|AB,A—aAS|aA|a,B—SBS|SB|BS|aAS|aA|a|bb,⑶由算法i和算法2,消除無用符號(此題沒有無用符號)；⑷轉化為等價的Chomsky范式的文法：將Si—ASB變換為S—AC,C—SB,將S—ASB變換為S—AC,將A—aAS|aA變換為A—ED|EA,D—AS,E—a,將B—SBS|aAS|aA|a|bb,變換為B—CS|ED|EA|FF,F—b,⑸由此得出符合題目要求的等價文法：Gi=({Si,S,A,B,C,D},{a,b},Pi,Si)，其中生成式Pi如下：Si—e|AC|AB,S—AC|AB,A—ED|EA|a,B—CS|SB|BS|ED|EA|a|FF,C—SB,D—AS,E—a,F—b.i5.將下列文法變換為等價的Greibach范式文法：(1)S—DD|a,D—SS|b解：將非終結符排序為S,D,S為低位,D為高位，⑴對于D—SS用S—DD|a代入得D—DDS|aS|b,用引理4.2.4,變化為D—aS|b|aSD'|bD',DDS|DSD',⑵將D生成式代入S生成式得S—aSD|bD|aSD'D|bD'D|a,⑶將D生成式代入D'生成式得DaSS|bS|aSD'S|bD'S|aSSD'|bSD'|aSD'SD'|bD'SD',⑷由此得出*價的Greibach范式文法：Gi=({S,D,D'},{a,b},Pi,S)，其中生成式Pi如下：S—aSD|bD|aSDD|bD'D|a,D—aS|b|aSD'|bD',DaSS|bS|aSD'S|bD'S|aSSD'|bSD'|aSD'SD'|bD'SD'.⑵Ai—A3b|A2a,A2—Aib|A2A2a|b,A3—Aia|A3A3b|a解：⑴轉化為等價的Chomsky范式的文法：Ai—A3A4|A2A5,A2-AiA4|A2A6|b,A3-AiA5|a3A7|a,A4—b,A5—a,A6—A2A5,A7—A3A4,⑵轉化為等價的Greibach范式的文法：將非終結符排序為Al,A2,A3,A4,A5,A1為低位A5為高位，①對于A2—A1A4，用A1—A3A4|A2A5代入得A2—A3A4A4|A2A5A4|A2A6|b,用引理4.2.4,變化為A2-A3A4A4|b|A3A4A4A2'|bA2',A2'fA5A4A2'A6A2'|A5A4|A6,②對于A3—A1A5,用Ai-A3A4|A2A5代入得A3fA3A4A5|A2A5A5|A3A7|a,A3生成式右邊第一個字符仍是較低位的非終結符，將A2生成式代入A3生成式得A3-A3A4A5|A3A4A4A5A5|bA5A5|A3A4A4A2'A5A5|bA2'A5A5|A3A7|a,用引理4.2.4,變化為A3—bA5A5|bA2'A5A5|a|bA5A5A3'|bA2'A5A5A3'|aA3'，A3'fA4A5|A4A4A5A5|A4A4A2'A5A5|A7|A4A5A3'|A4A4A5A5A3'|A4A4A2A5A5A3'|A7A3',③對于A6fA2A5，將A2生成式代入A6生成式得A6-A3A4A4A5|bA5|A3A4A4A2'A5|bA2^5,A6生成式右邊第一個字符仍是較低位的非終結符，將A3生成式代入A6生成式得A6-bA5A5A4A4A5|bA2A5A5A4A4A5|aA4A4A5|bA5A5A3'A4A4A5|bA2A5A5A3A4A4A5|aA3A4A4A5|bA5A5A4A4A2'A5|bA2'A5A5A4A4A2'A5|aA4A4A2A5|bA5A5A3'A4A4A2'A5|bA2'A5A5A3'A4A4A2A5|aA3A4A4A2A5|bA2'A5|bA5,④對于A7fA3A4,將A3生成式代入A7生成式得A7-bA5A5A4|bA2'A5A5A4|aA41bA5A5A3'A4|bA2'A5A5A3'A4|aA3'A4,⑤將A5,A6生成式代入A2,生成式得A2’—aA4A2'IbA5A5A4A4A5A2'|bA2A5A5A4A4A5A2'|aA4A4A5A2'|bA5A5A3'A4A4A5A2'|bA2'A5A5A3'A4A4A5A2'|aA3'A4A4A5A2'|bA5A5A4A4A2'A5A2'|bA2A5A5A4A4A2A5A2'|aA4A4A2'A5A2'|bA5A5A3'A4A4A2A5A2'|bA2'A5A5A3'A4A4A2A5A2'|aA3'A4A4A2'A5A2'|bA2A5A2'|bA5A2'|aA4|bA5A5A4A4A5|bA2'A5A5A4A4A5|aA4A4A5|bA5A5A3'A4A4A5|bA2'A5A5A3A4A4A5|aA3'A4A4A5|bA5A5A4A4A2'A5|bA2A5A5A4A4A2A5|aA4A4A2'A5|bA5A5A3'A4A4A2'A5|bA2A5A5A3A4A4A2'A5|aA3'A4A4A2A5|bA2A5|bA5,將A4,A7生成式代入A3,生成式得A3'—aA5|aA4A5A5|aA4A2A5A5|aA5A3'|aA4A5A5A3'|aA4A2'A5A5A3'|bA5A5A4|bA2A5A5A4|aA4|bA5A5A3A4|bA2'A5A5A3'A4|aA3A4|bA5A5A4A3'|bA2A5A5A4A3'aA4A3'|bA5A5A3A4A3'|bA2'A5A5A3‘A4A3'3A3A4A3',⑶由此得出等價的Greibach范式文法：Gi=({S,D,D'},{a,b},Pi,S)，其中生成式Pi如下：Ai—A3A4|A2A5,A2-A3A4A4|b|A3A4A4A2'|bA2',A3-bA5A5|bA2'A5A5|a|bA5A5A31bA2'A5A5A3'|aA3'，A4—b,A5—a,A6-bA5A5A4A4A5|bA2A5A5A4A4A5|aA4A4A5|bA5A5A3'A4A4A5|bA2A5A5A3A4A4A5|aA3A4A4A5|bA5A5A4A4A2'A5|bA2'A5A5A4A4A2'A5|aA4A4A2A5|bA5A5A3'A4A4A2'A5|bA2'A5A5A3A4A4A2A|aA3A4A4A2A5|bA2^5|bA5,A7-bA5A5A4|bA2'A5A5A4|aA41bA5A5A3'A4|bA2'A5A5A3'A4|aA3'A4,A2'faA4A2'IbA5A5A4A4A5A2'|bA2A5A5A4A4A5A2'|aA4A4A5A2'|bA5A5A3'A4A4A5A2'|bA2'A5A5A3'A4A4A5A2'|aA3'A4A4A5A2'|bA5A5A4A4A2'A5A2'|bA2A5A5A4A4A2A5A2'|aA4A4A2'A5A2'|bA5A5A3'A4A4A2A5A2'|bA2'A5A5A3'A4A4A2A5A2'|aA3'A4A4A2'A5A2'|bA2A5A2'|bA5A2'|aA4|bA5A5A4A4A5|bA2'A5A5A4A4A5|aA4A4A5|bA5A5A3'A4A4A5|bA2'A5A5A3A4A4A5|aA3'A4A4A5|bA5A5A4A4A2'A5|bA2A5A5A4A4A2A5|aA4A4A2'A5|bA5A5A3'A4A4A2'A5|bA2A5A5A3A4A4A2'A5|aA3'A4A4A2A5|bA2A5|bA5,A3'—aA5|aA4A5A5|aA4A2A5A5|aA5A3'|aA4A5A5A3'|aA4A2'A5A5A3'|bA5A5A4|bA2A5A5A4|aA4|bA5A5A3A4|bA2'A5A5A3'A4|aA3A4|bA5A5A4A3'|bA2A5A5A4A3'aA4A3'|bA5A5A3'A4A3'|bA2'A5A5A3‘A4A3'3A3A4A3'..設文法G有如下得生成式：S-aDD,D-aS|bS|a,構造等價的下推自動機.解：根據P162-163的算法，構造下推自動機M,使M按文法G的最左推導方式工作.設M=(Q,T,T,B,qo,Zo,F),其中Q={qo，qf},T={a,b},r={a,b,D,S},Zo=S,F={qf},B定義如下：B(qo,￡,S)={(qo,aDD)},TOC\o"1-5"\h\zB(qo,e,D)={(qo,aS),(qo,bS),(qo,a)},B(qo,a,a)={(qo,￡)},B(qo,e,e)={(qf,￡)}..給出產生語言L={aibjck|i,j,k>O且i=j或者j=k}的上下文無關文法.你給出的文法是否具有二義性畏什么？解：G=({S,A,B,C,D,E},{a,b,c},P,S)P:S—AD|EB,A—aAb|￡,B—bBc|￡,D—cD|￡,E—aE|&文法具有二義性。因為當句子3中a,b,c個數相同時，對于①存在兩個不同的最左(右)推導。如abcwL,存在兩個不同的最左推導—AD=aAbD=abD=abcC=abc及S=^EBnaE—aBnabBuabc。.設下推自動機M=({q0,qi},{a,b},{Z0,X},B,q0,Z0,6)，其中B如下:B(q0,b,Z0)={(q0,XZ0)},B(q。,￡,Z0)={(q0,￡)},AB(q0,b,X)={(q0,XX)},B(qi,b,X)={(q1,￡)},B(q0,b,X)={(q1,X)},B(qi,a,Z0)={(q0,Z0)},試構造文法G產生的語言L(G)=L(M).解：在G中，N={[q0,Z0,q0],[q0,Z0,qi],[q0,X,q0],[q0,X,qi],[q1,Z0,q0],[ql,Z0,qi],[ql,X,q0],[qi,X,qi]}.⑴S生成式有S—[q0,Z0,q0],S-[q0,Z0,qi],根據B(q0,b,Z0)={(q0,XZ0)}，則有[q0,Z0,q0]—b[q0,X,qo][qo,Z0,q0],[q0,Z0,q0]一b[q0,X,qi][qi,Z0,q0],[q0,Z0,qi]一b[q0,X,q0][q0,Z0,qi],[q0,Z0,qi]一b[q0,X,q1][qi,Z0,qi],因為有B(q0,b,X)={(q0,XX)},則有[q0,X,q0]一b[q0,X,q0][q°,X,q0],[q0,X,q0]-b[q0,X,qi][qi,X,q°],[q0,X,qi]一b[q0,X,qo][qo,X,q1],[q0,X,qi]-b[q0,X,qi][qi,X,qi],因為有B(q0,a,X)={(q1,X)},則有[q0,X,q0]一a[q1,X,q0],[q0,X,qi]-^a[qi,X,qi],因為有B(qi,a,Z0)={(q0,Z0)},則有[qi,Z0,q0]—a[q0,Z0,qo],[qi,Z0,q1]-^a[q0,Z0,qi],因為有B(q0,￡,Z0)={(q0,e)},則有[q0,Z0,q0]一&,因為有B(qi,b,X)={(q1,e)},則有[qi,X,qi]一￡⑵利用算法1和算法2,消除無用符號后，得出文法G產生的語言L(G)={N,T,P,S}其中N={S,[q0,Z0,q0],[qi,Z0,q0],[qi,X,qi],[q0,X,qi]},T={a,b},生成式P如下:S—[q0,Z0,qo],[q0,Z0,q0]一b[q0,X,qi][qi,Z0,q0],[q0,X,qi]-b[q0,X,q〔][q〔,X,q1],[q0,X,qi]-^a[qi,X,qi],[qi,Z0,q0]—a[q0,Z0,q0],[q0,Z0,q0]一&,[q0,Z0,q0]一e..證明下列語言不是上下文無關語言：{anbncm|m<n};證明：假設L是上下文無關語言，由泵浦引理，取常數p,當3cL且131Ap時，可取==apbpcp，將3寫為3=3132303334,同時滿足|323033|<p32和33不可能同時分別包含a和C,因為在這種情況下，有|323033|>p；⑵如果32和⑴3者B只包含a(b),即323033=aj(bj)(j&p),則當iw1時，3132‘3033’34中會出現a的個數與b的個數不等；如果32和33都只包含c,即323033=cj(j&p),當i大于1時，3132303334中會出現c的個數大于a的個數(b的個數)；(3)如果32和33分別包含a和b(b和c),當i=0時3132,3033%4中會出現a,b的個數小于c的個數(或a,b個數不等)這些與假設矛盾，故L不是上下文無關語言.⑵{ak|k是質數};證明：假設L是上下文無關語言，由泵浦引理，取常數p,當3cL且131Ap時，可取3=ak(kAp且kW1),將3寫為3=3132303334,同時滿足|323033|&p,且13233|=j>1，貝U當i=k+1時，|3132,3033’34|=k+(i-1)*j=k+k*j=k*(1+j),k*(1+j)至少包含因子k且kw1，因此必定不是質數，即3132i303334不屬于L.這與假設矛盾，故L不是上下文無關語言.⑶由a,b,c組成的字符串且是含有a,b,c的個數相同的所有字符串.證明：假設L是上下文無關語言，由泵浦引理，取常數p,當3cL且131Ap時，可取==akbkck(knp),將3寫為3=3132303334,同時滿足|323033|<p(1)32和33不可能同時分別包含a和c,因為在這種情況下，有|323033|>p；⑵如果32和33者B只包含a(b或c),即323033=aj(bj或cj)(j<p),則當iw1時，3132i3033,34中會出現a,b,c的個數不再相等；(3)如果32和33分別包含a和b(b和c),3132i3033i34中會出現a,b的個數與c的不等；這些與假設矛盾，故L不是上下文無關語言..設G是Chomsky范式文法，存在3cL(G),求在邊緣為3的推導樹中，最長的路徑長度與3的長度之間的關系.解：設邊緣為3的推導樹中