形式語言與自動機理論試題

/形式語言與自動機理論試題一、按要求完成下列填空給出集合{Φ,{Φ}}和集合{ε,0,00}的冪集〔2x4<1>{Φ,{Φ},{{Φ}},{Φ,{Φ}}}<2>{Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}設(shè)∑={0,1},請給出∑上的下列語言的文法〔2x5所有包含子串01011的串S→X01011YX→ε|0X|1XY→ε|0Y|1Y<2>所有既沒有一對連續(xù)的0.也沒有一對連續(xù)的1的串A→ε|A’|A"A’→0|01|01A’A"→1|10|10A"構(gòu)造識別下列語言的DFA2x6<1>{x|x?{0.1}+且x以0開頭以1結(jié)尾}〔設(shè)置陷阱狀態(tài).當(dāng)?shù)谝粋€字符為1時.進入陷阱狀態(tài)<2>{x|x{0.1}+且x的第十個字符為1}〔設(shè)置一個陷阱狀態(tài).一旦發(fā)現(xiàn)x的第十個字符為0.進入陷阱狀態(tài)二、判斷〔正確的寫T.錯誤的寫F5x21.設(shè)和是集合{a,b,c,d,e}上的二元關(guān)系.則<T>任取<x.,y>,其中x,y.使得。2.對于任一非空集合A.Φ<T>3.文法G：SA|ASAa|b|c|d|e|f|g是RG<F>4.3型語言2型語言1型語言0型語言<T>5.s〔rs+sr=rrs〔rrs<F>不成立.假設(shè)r,s分別是表示語言R.S的正則表達式.例如當(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的至少兩個不同的推導(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四、判斷語言{|n>=1}是否為RL.如果是.請構(gòu)造出它的有窮描述<FA,RG或者RL；如果不是.請證明你的結(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此時有u=.w=從而有uvw=當(dāng)i=2時.有uvw=又因為k>=1,所以N+k>N這就是說不屬于L.這與泵引理矛盾。所以.L不是RL。五、構(gòu)造等價于下圖所示DFA的正則表達式。<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請根據(jù)此定義.給出M處理字符串00001000,10000的過程中ID的變化?！?0分解：處理輸入串00001000的過程中經(jīng)歷的ID變化序列如下：00001000000010000000100000001000000010000處理輸入串10000的過程中經(jīng)歷的ID變化序列如下：100001000001000010000100001000010000B七、根據(jù)給定的NFA.構(gòu)造與之等價的DFA?！?4分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)造下列語言的文法。<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>＝{ω│ω中含有相同個數(shù)的a和b.且ω非空}。證：觀察發(fā)現(xiàn)A的產(chǎn)生式A→bAA中的bA可以用S來代替.同樣B的產(chǎn)生式B→aBB中的aB也可以用S代替。這樣原來的文法可以化為如下的形式：S→aB│bAA→a│aS│SAB→b│bS│SB進一步地.可以把產(chǎn)生式A→aS中的S代換.把文法化為如下的形式：S→aB│bAA→a│aaB│abA│SAB→b│baB│bbA│SB7．設(shè)DFAM=.證明：對于注：采用歸納證明的思路證明：<周期律02282067>首先對y歸納.對任意x來說.|y|=0時.即y=根據(jù)DFA定義,故原式成立。當(dāng)|y|=n時.假設(shè)原式成立.故當(dāng)|y|=n+1時.不妨設(shè)y=wa,|w|=n,|a|=1根據(jù)DFA定義.故原式成立.同理可證.對任意的y來說.結(jié)論也是成立的。綜上所述.原式得證*******************************************************************************8．證明:對于任意的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 對任意xΣ*xL<M2>=Σ*—L〔M1δ<q,x>Q—F1δ〔q,xQ并且δ〔q,xF1xΣ*并且xL<M1>xΣ*—L〔M110、構(gòu)造識別下列語言的NFA根據(jù)給定的NFA.構(gòu)造與之等價的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等價的DFA13．試給出一個構(gòu)造方法.對于任意的NFA.構(gòu)造NFA.使得注：轉(zhuǎn)化成相應(yīng)的DFA進行處理.然后可參考第8題的思路證明：首先構(gòu)造一個與NFA等價的DFA.根據(jù)定理3.1〔P106. 構(gòu)造其中在此基礎(chǔ)上.即取所有確定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。為了證明.我們在的基礎(chǔ)上.其中.即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然則又因為故.故同理容易證明故.又因為.故可知.構(gòu)造的是符合要求的。P12915.<1>、〔2〔1根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù).起始狀態(tài)q0的閉包為-CLOSURE〔q0={q0,q2}。由此對以后每輸入一個字符后得到的新狀態(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}.因為q3為終止?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}因為各狀態(tài)均含有終止?fàn)顟B(tài).所以q0,q1.q2.q3,q4均為終止?fàn)顟B(tài)注：本題沒有必要按照NFA到DFA轉(zhuǎn)化的方法來做.而且從-NFA到NFA轉(zhuǎn)化時狀態(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、證明對于的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}對于q∈Q1,a∈∑1δ<q,a>=δ1<q,a>對于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>時δ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>時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>因為Q1與Q2的交集為空而且δ〔q0,x∈FF=F1∪F2則δ<q01,x>=δ1<q01,x>∈F1因此x∈L<M1>如果是δ<q02,x>因為Q1與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證明：對于任意的FA.證明：令,其中δ的定義為：1>對"q∈Q1-{f1}.a∈∑∪{ε}δ<q.a>=δ1<q.a>；2>對"q∈Q2-{f2}.a∈∑∪{ε}δ<q.a>=δ2<q.a>；3>δ<f1.ε>={q02}要證.只需證明.證明2>再證明*******************************************************************************〔吳丹02282090FAM的移動函數(shù)定義