版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
/形式語言與自動機理論試題一、按要求完成下列填空給出集合{Φ,{Φ}}和集合{ε,0,00}的冪集〔2x4<1>{Φ,{Φ},{{Φ}},{Φ,{Φ}}}<2>{Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}設∑={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"構造識別下列語言的DFA2x6<1>{x|x?{0.1}+且x以0開頭以1結尾}〔設置陷阱狀態(tài).當?shù)谝粋€字符為1時.進入陷阱狀態(tài)<2>{x|x{0.1}+且x的第十個字符為1}〔設置一個陷阱狀態(tài).一旦發(fā)現(xiàn)x的第十個字符為0.進入陷阱狀態(tài)二、判斷〔正確的寫T.錯誤的寫F5x21.設和是集合{a,b,c,d,e}上的二元關系.則<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>不成立.假設r,s分別是表示語言R.S的正則表達式.例如當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>*,結論不成立三、設文法G的產生式集如下.試給出句子aaabbbccc的至少兩個不同的推導〔12分。bB→bbCB→BCbC→bccC→cc推導一:S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc推導二:S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaaBBCCBC=>aaaBBCBCC=>aaabBCBCC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc四、判斷語言{|n>=1}是否為RL.如果是.請構造出它的有窮描述<FA,RG或者RL;如果不是.請證明你的結論〔12分解:設L={|n>=1}。假設L是RL.則它滿足泵引理。不妨設N是泵引理所指的僅依賴于L的正整數(shù).取Z=顯然.Z∈L。按照泵引理所述.必存在u.v.w。由于|uv|<=N,并且|v|>=1.所以v只可能是由0組成的非空串。不妨設v=.k>=1此時有u=.w=從而有uvw=當i=2時.有uvw=又因為k>=1,所以N+k>N這就是說不屬于L.這與泵引理矛盾。所以.L不是RL。五、構造等價于下圖所示DFA的正則表達式。<12分>
SSq1q0q2q310001110答案<之一>:<01+<1+00><<1+00*1>0>*<<1+00*1>1>>*<+<1+00><<1+00*1>0>*00*>qq1q0q2q310001110XY預處理:去掉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*>六、設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的過程中經歷的ID變化序列如下:00001000000010000000100000001000000010000處理輸入串10000的過程中經歷的ID變化序列如下:100001000001000010000100001000010000B七、根據(jù)給定的NFA.構造與之等價的DFA。〔14分NFAM的狀態(tài)轉移函數(shù)如下表狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0{q0,q1}{q0,q2}{q0,q2}q1{q3,q0}{q2}q2{q3,q1}{q2,q1}終止狀態(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]終止狀態(tài)[q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q2]終止狀態(tài)[q0,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]終止狀態(tài)[q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]參考題目1、設.構造下列語言的文法。<1>。解答:。<2>。解答:。<3>。解答:S→aAB|aSABBA→ABaB→abbB→bbbA→baaA→aa<4>。解答:。<5>。解答:。<6>。解答:。<7>。解答:。<8>。解答:。2、給定RG:..試分別構造滿足下列要求的RGG.并證明你的結論。解:P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1}證明略。解:P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1}證明略。3、設文法G有如下產生式:S→aB│bAA→a│aS│bAAB→b│bS│aBB證明L<G>={ω│ω中含有相同個數(shù)的a和b.且ω非空}。證:觀察發(fā)現(xiàn)A的產生式A→bAA中的bA可以用S來代替.同樣B的產生式B→aBB中的aB也可以用S代替。這樣原來的文法可以化為如下的形式:S→aB│bAA→a│aS│SAB→b│bS│SB進一步地.可以把產生式A→aS中的S代換.把文法化為如下的形式:S→aB│bAA→a│aaB│abA│SAB→b│baB│bbA│SB7.設DFAM=.證明:對于注:采用歸納證明的思路證明:<周期律02282067>首先對y歸納.對任意x來說.|y|=0時.即y=根據(jù)DFA定義,故原式成立。當|y|=n時.假設原式成立.故當|y|=n+1時.不妨設y=wa,|w|=n,|a|=1根據(jù)DFA定義.故原式成立.同理可證.對任意的y來說.結論也是成立的。綜上所述.原式得證*******************************************************************************8.證明:對于任意的DFAM1=<Q,Σ,δ,q0,F1>存在DFAM2=<Q,Σ,δ,q0,F2>,使得L<M2>=Σ*—L〔M1。 證明:〔1構造M2。 設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、構造識別下列語言的NFA根據(jù)給定的NFA.構造與之等價的DFA.〔1NFAM1的狀態(tài)轉移函數(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}終止狀態(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]終止狀態(tài)[q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q1,q2]終止狀態(tài)[q0,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q2]終止狀態(tài)[q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]圖3-9所示NFA等價的DFA13.試給出一個構造方法.對于任意的NFA.構造NFA.使得注:轉化成相應的DFA進行處理.然后可參考第8題的思路證明:首先構造一個與NFA等價的DFA.根據(jù)定理3.1〔P106. 構造其中在此基礎上.即取所有確定化后不是終結狀態(tài)的狀態(tài)為的終結狀態(tài)。為了證明.我們在的基礎上.其中.即所有確定化后的狀態(tài)都為終結狀態(tài)。顯然則又因為故.故同理容易證明故.又因為.故可知.構造的是符合要求的。P12915.<1>、〔2〔1根據(jù)NFAM3的狀態(tài)轉移函數(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為終止狀態(tài).所以q2={q0,q1.q2.q3}為終止狀態(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)均含有終止狀態(tài).所以q0,q1.q2.q3,q4均為終止狀態(tài)注:本題沒有必要按照NFA到DFA轉化的方法來做.而且從-NFA到NFA轉化時狀態(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〔終止狀態(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〔終止狀態(tài)空{q0}16、證明對于的FAM1=<Q1,∑1,δ1,q01,F1>.FAM1=<Q2,∑2,δ2,q02,F2>.存在FAM.使得L<M>=L<M1>∪L<M2>證明:不妨設Q1與Q2的交集為空構造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>設x∈L<M1>∪L<M2>.從而有x∈L<M1>或者x∈L<M2>.當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>同理可證當x∈L<M2>時x∈L<M>故L<M1>∪L<M2>∈L<M>2>再證明L<M>∈L<M1>∪L<M2>設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ù)定義
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 退休會計師財務審計合同
- 2024政府采購的消防設備采購合同3篇
- 2024年網絡營銷推廣服務合同標的及推廣策略具體規(guī)定
- 2024年錨桿工程特種設計與施工承包合同3篇
- 2025版高端服裝定制加工合同樣本3篇
- 二零二五年品牌授權合同保密條款3篇
- 2024年貨物出口銷售合同及付款條件3篇
- 2024年度國家助學貸款借款合同(擔保抵押)3篇
- 2024房屋一半產權轉讓合同
- 2024年糧食儲備庫租賃合同模板版B版
- 2024信息技術應用創(chuàng)新信息系統(tǒng)適配改造成本度量
- 廣東省廣州市2025屆高三上學期12月調研測試(零模)英語 含解析
- 陜西測繪地理信息局所屬事業(yè)單位2025年上半年招聘87人和重點基礎提升(共500題)附帶答案詳解
- 保險學期末試題及答案
- 高一數(shù)學上學期期末模擬試卷01-【中職專用】2024-2025學年高一數(shù)學上學期(高教版2023基礎模塊)(解析版)
- 嚴重精神障礙患者隨訪服務記錄表
- 2024-2025學年人教版八年級上冊地理期末測試卷(一)(含答案)
- 統(tǒng)編版(2024新版)七年級上冊道德與法治第四單元綜合測試卷(含答案)
- 滬教版英語小學六年級上學期期末試題與參考答案(2024-2025學年)
- 北京市海淀區(qū)2023-2024學年四年級上學期語文期末試卷
- 混凝土企業(yè)安全培訓
評論
0/150
提交評論