形式語(yǔ)言與自動(dòng)機(jī)理論試題

/形式語(yǔ)言與自動(dòng)機(jī)理論試題一、按要求完成下列填空給出集合{Φ,{Φ}}和集合{ε,0,00}的冪集〔2x4<1>{Φ,{Φ},{{Φ}},{Φ,{Φ}}}<2>{Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}設(shè)∑={0,1},請(qǐng)給出∑上的下列語(yǔ)言的文法〔2x5所有包含子串01011的串S→X01011YX→ε|0X|1XY→ε|0Y|1Y<2>所有既沒有一對(duì)連續(xù)的0.也沒有一對(duì)連續(xù)的1的串A→ε|A’|A"A’→0|01|01A’A"→1|10|10A"構(gòu)造識(shí)別下列語(yǔ)言的DFA2x6<1>{x|x?{0.1}+且x以0開頭以1結(jié)尾}〔設(shè)置陷阱狀態(tài).當(dāng)?shù)谝粋€(gè)字符為1時(shí).進(jìn)入陷阱狀態(tài)<2>{x|x{0.1}+且x的第十個(gè)字符為1}〔設(shè)置一個(gè)陷阱狀態(tài).一旦發(fā)現(xiàn)x的第十個(gè)字符為0.進(jìn)入陷阱狀態(tài)二、判斷〔正確的寫T.錯(cuò)誤的寫F5x21.設(shè)和是集合{a,b,c,d,e}上的二元關(guān)系.則<T>任取<x.,y>,其中x,y.使得。2.對(duì)于任一非空集合A.Φ<T>3.文法G：SA|ASAa|b|c|d|e|f|g是RG<F>4.3型語(yǔ)言2型語(yǔ)言1型語(yǔ)言0型語(yǔ)言<T>5.s〔rs+sr=rrs〔rrs<F>不成立.假設(shè)r,s分別是表示語(yǔ)言R.S的正則表達(dá)式.例如當(dāng)R={0}.S={1},L<s<rs+s>*r>是以1開頭的字符串.而L<rr*s<rr*s>*>是以0開頭的字符串.L<s<rs+s>*r>L<rr*s<rr*s>*>所以s<rs+s>*rrr*s<rr*s>*,結(jié)論不成立三、設(shè)文法G的產(chǎn)生式集如下.試給出句子aaabbbccc的至少兩個(gè)不同的推導(dǎo)〔12分。bB→bbCB→BCbC→bccC→cc推導(dǎo)一：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc推導(dǎo)二：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaaBBCCBC=>aaaBBCBCC=>aaabBCBCC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc四、判斷語(yǔ)言{|n>=1}是否為RL.如果是.請(qǐng)構(gòu)造出它的有窮描述<FA,RG或者RL；如果不是.請(qǐng)證明你的結(jié)論〔12分解：設(shè)L={|n>=1}。假設(shè)L是RL.則它滿足泵引理。不妨設(shè)N是泵引理所指的僅依賴于L的正整數(shù).取Z=顯然.Z∈L。按照泵引理所述.必存在u.v.w。由于|uv|<=N,并且|v|>=1.所以v只可能是由0組成的非空串。不妨設(shè)v=.k>=1此時(shí)有u=.w=從而有uvw=當(dāng)i=2時(shí).有uvw=又因?yàn)閗>=1,所以N+k>N這就是說不屬于L.這與泵引理矛盾。所以.L不是RL。五、構(gòu)造等價(jià)于下圖所示DFA的正則表達(dá)式。<12分>

SSq1q0q2q310001110答案<之一>：<01+<1+00><<1+00*1>0>*<<1+00*1>1>>*<+<1+00><<1+00*1>0>*00*>qq1q0q2q310001110XY預(yù)處理：去掉q3：qq1q0q21011+00*10XY00*去掉q1：qq0q21+00<1+00*1>0XY00*<1+00*1>101q0XYq0XY+<1+00><<1+00*1>0>*00*01+<1+00><<1+00*1>0>*<<1+00*1>1>去掉q0：XXY<01+<1+00><<1+00*1>0>*<<1+00*1>1>>*<+<1+00><<1+00*1>0>*00*>六、設(shè)M=〔{}.{0,1}.{0,1.B}.{δ}.,B,{},其中δ的定義如下：δ〔.0=〔.0.Rδ〔.1=〔.1.Rδ〔.0=〔.0.Rδ〔.B=〔.B.R請(qǐng)根據(jù)此定義.給出M處理字符串00001000,10000的過程中ID的變化?！?0分解：處理輸入串00001000的過程中經(jīng)歷的ID變化序列如下：00001000000010000000100000001000000010000處理輸入串10000的過程中經(jīng)歷的ID變化序列如下：100001000001000010000100001000010000B七、根據(jù)給定的NFA.構(gòu)造與之等價(jià)的DFA。〔14分NFAM的狀態(tài)轉(zhuǎn)移函數(shù)如下表狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0{q0,q1}{q0,q2}{q0,q2}q1{q3,q0}{q2}q2{q3,q1}{q2,q1}終止?fàn)顟B(tài)q3{q3,q2}{q3}{q0}解答：狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0[q0,q1][q0,q2][q0,q2][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q1,q2,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,q3][q0,q1,q2]終止?fàn)顟B(tài)[q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q2]終止?fàn)顟B(tài)[q0,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]終止?fàn)顟B(tài)[q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]參考題目1、設(shè).構(gòu)造下列語(yǔ)言的文法。<1>。解答：。<2>。解答：。<3>。解答：S→aAB|aSABBA→ABaB→abbB→bbbA→baaA→aa<4>。解答：。<5>。解答：。<6>。解答：。<7>。解答：。<8>。解答：。2、給定RG：..試分別構(gòu)造滿足下列要求的RGG.并證明你的結(jié)論。解：P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1}證明略。解：P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1}證明略。3、設(shè)文法G有如下產(chǎn)生式：S→aB│bAA→a│aS│bAAB→b│bS│aBB證明L<G>＝{ω│ω中含有相同個(gè)數(shù)的a和b.且ω非空}。證：觀察發(fā)現(xiàn)A的產(chǎn)生式A→bAA中的bA可以用S來(lái)代替.同樣B的產(chǎn)生式B→aBB中的aB也可以用S代替。這樣原來(lái)的文法可以化為如下的形式：S→aB│bAA→a│aS│SAB→b│bS│SB進(jìn)一步地.可以把產(chǎn)生式A→aS中的S代換.把文法化為如下的形式：S→aB│bAA→a│aaB│abA│SAB→b│baB│bbA│SB7．設(shè)DFAM=.證明：對(duì)于注：采用歸納證明的思路證明：<周期律02282067>首先對(duì)y歸納.對(duì)任意x來(lái)說.|y|=0時(shí).即y=根據(jù)DFA定義,故原式成立。當(dāng)|y|=n時(shí).假設(shè)原式成立.故當(dāng)|y|=n+1時(shí).不妨設(shè)y=wa,|w|=n,|a|=1根據(jù)DFA定義.故原式成立.同理可證.對(duì)任意的y來(lái)說.結(jié)論也是成立的。綜上所述.原式得證*******************************************************************************8．證明:對(duì)于任意的DFAM1=<Q,Σ,δ,q0,F1>存在DFAM2=<Q,Σ,δ,q0,F2>,使得L<M2>=Σ*—L〔M1。 證明：〔1構(gòu)造M2。 設(shè)DFAM1=<Q,Σ,δ,q0,F1>取DFAM2=<Q,Σ,δ,q0,Q—F1> 〔2證明L<M2>=Σ*—L〔M1 對(duì)任意xΣ*xL<M2>=Σ*—L〔M1δ<q,x>Q—F1δ〔q,xQ并且δ〔q,xF1xΣ*并且xL<M1>xΣ*—L〔M110、構(gòu)造識(shí)別下列語(yǔ)言的NFA根據(jù)給定的NFA.構(gòu)造與之等價(jià)的DFA.〔1NFAM1的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0{q0,q1}{q0,q2}{q0,q2}q1{q3,q0}{q2}q2{q3,q1}{q2,q1}終止?fàn)顟B(tài)q3{q3,q2}{q3}{q0}解答：狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0[q0,q1][q0,q2][q0,q2][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q1,q2,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,q3][q0,q1,q2]終止?fàn)顟B(tài)[q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q1,q2]終止?fàn)顟B(tài)[q0,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q2]終止?fàn)顟B(tài)[q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]圖3-9所示NFA等價(jià)的DFA13．試給出一個(gè)構(gòu)造方法.對(duì)于任意的NFA.構(gòu)造NFA.使得注：轉(zhuǎn)化成相應(yīng)的DFA進(jìn)行處理.然后可參考第8題的思路證明：首先構(gòu)造一個(gè)與NFA等價(jià)的DFA.根據(jù)定理3.1〔P106. 構(gòu)造其中在此基礎(chǔ)上.即取所有確定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。為了證明.我們?cè)诘幕A(chǔ)上.其中.即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然則又因?yàn)楣?故同理容易證明故.又因?yàn)?故可知.構(gòu)造的是符合要求的。P12915.<1>、〔2〔1根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù).起始狀態(tài)q0的閉包為-CLOSURE〔q0={q0,q2}。由此對(duì)以后每輸入一個(gè)字符后得到的新狀態(tài)再做閉包.得到下表：〔陶文婧02282085狀態(tài)01{q0,q2}{q0,q1.q2}{q0,q1.q2.q3}{q0,q1.q2}{q0,q1.q2.q3}{q0,q1.q2.q3}{q0,q1.q2.q3}{q0,q1.q2.q3}{q0,q1.q2.q3}q0={q0,q2}.q1={q0,q1.q2}.q2={q0,q1.q2.q3}.因?yàn)閝3為終止?fàn)顟B(tài).所以q2={q0,q1.q2.q3}為終止?fàn)顟B(tài)〔2用上述方法得狀態(tài)01{q1,q3}{q3.q2}{q0,q1.q2.q3}{q3.q2}{q3.q2}{q0,q1.q3}{q0,q1.q2.q3}{q1.q2.q3}{q0,q1.q2.q3}{q0,q1.q3}{q1.q2.q3}{q0,q1.q2.q3}{q1.q2.q3}{q3.q2}{q0,q1.q2.q3}q0={q1,q3}.q1={q3.q2}.q2={q0,q1.q2.q3}.q3={q0,q1.q3}.q4={q1.q2.q3}因?yàn)楦鳡顟B(tài)均含有終止?fàn)顟B(tài).所以q0,q1.q2.q3,q4均為終止?fàn)顟B(tài)注：本題沒有必要按照NFA到DFA轉(zhuǎn)化的方法來(lái)做.而且從-NFA到NFA轉(zhuǎn)化時(shí)狀態(tài)沒有必要改變.可以完全采用-NFA中的狀態(tài)如〔1狀態(tài)01q0<開始狀態(tài)>{q0,q1.q2q3}{q0,q1.q2.q3}q1{q0,q1.q2.q3}{q1.q2.q3}q2{q0,q1.q2.q3}{q1.q2.q3}q3〔終止?fàn)顟B(tài){q0,q1.q2.q3}{q0,q1.q2.q3}<2>狀態(tài)01q0<開始狀態(tài)>{q1q2q3.}{q0,q1.q2.q3}q1{q2}{q1.q2}q2{.q2.q3}{q0,q2.q3}q3〔終止?fàn)顟B(tài)空{(diào)q0}16、證明對(duì)于的FAM1=<Q1,∑1,δ1,q01,F1>.FAM1=<Q2,∑2,δ2,q02,F2>.存在FAM.使得L<M>=L<M1>∪L<M2>證明：不妨設(shè)Q1與Q2的交集為空構(gòu)造M=〔Q1∪Q2∪{q0},∑,δ,q0,F其中：1∑=∑1∪∑2F=F1∪F22>δ<q0,ε>={q01,q02}對(duì)于q∈Q1,a∈∑1δ<q,a>=δ1<q,a>對(duì)于q∈Q2,a∈∑2,δ<q,a>=δ2<q,a>證明：1首先證L<M1>∪L<M2>∈L<M>設(shè)x∈L<M1>∪L<M2>.從而有x∈L<M1>或者x∈L<M2>.當(dāng)x∈L<M1>時(shí)δ1<q01,x>∈F1由M的定義可得：δ〔q0,x=δ〔q0,εx=δ<δ<q0,ε>,x>=δ<{q01,q02},x>=δ<q01,x>∪δ<q02,x>=δ1<q01,x>∪δ<q01,x>∈F1∪δ<q01,x>即x∈L<M>同理可證當(dāng)x∈L<M2>時(shí)x∈L<M>故L<M1>∪L<M2>∈L<M>2>再證明L<M>∈L<M1>∪L<M2>設(shè)x∈L<M>則δ〔q0,x∈F由M的定義：δ〔q0,x=δ〔q0,εx=δ<δ<q0,ε>,x>=δ<{q01,q02},x>=δ<q01,x>∪δ<q02,x>如果是δ<q01,x>因?yàn)镼1與Q2的交集為空而且δ〔q0,x∈FF=F1∪F2則δ<q01,x>=δ1<q01,x>∈F1因此x∈L<M1>如果是δ<q02,x>因?yàn)镼1與Q2的交集為空而且δ〔q0,x∈FF=F1∪F2則δ<q02,x>=δ2<q02,x>∈F1因此x∈L<M2>因此x∈L<M1>∪L<M2>L<M>∈L<M1>∪L<M2>得證因此L<M>=L<M1>∪L<M2>17證明：對(duì)于任意的FA.證明：令,其中δ的定義為：1>對(duì)"q∈Q1-{f1}.a∈∑∪{ε}δ<q.a>=δ1<q.a>；2>對(duì)"q∈Q2-{f2}.a∈∑∪{ε}δ<q.a>=δ2<q.a>；3>δ<f1.ε>={q02}要證.只需證明.證明2>再證明*******************************************************************************〔吳丹02282090FAM的移動(dòng)函數(shù)定義