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

《形式語言與自動機理論試題.doc》由會員分享，可在線閱讀，更多相關(guān)《形式語言與自動機理論試題.doc（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

形式語言與自動機理論試題 一、按要求完成下列填空 1. 給出集合{Φ,{Φ}}和集合{ε,0,00}的冪集 （2x4） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 設∑={0,1},請給出∑上的下列語言的文法 （2x5） (1) 所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既沒有一對連續(xù)的0，也沒有一對連續(xù)的1的串 A→ε|A’|A” A’ →0|01|01A’ A” →1|10|10A” 3. 構(gòu)造識別下列語言的DFA 2x6 (1) {x|x{0，1}+且x以0開頭以1結(jié)尾} （設置陷阱狀態(tài)，當?shù)谝粋€字符為1時，進入陷阱狀態(tài)） (2) {x|x{0，1}+且x的第十個字符為1} （設置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個字符為0，進入陷阱狀態(tài)） 二、判斷（正確的寫T，錯誤的寫F） 5x2 1.設和是集合{a,b,c,d,e}上的二元關(guān)系，則 ( T ) 任取(x.,y),其中x,y，使得。 2.對于任一非空集合A，Φ ( T ) 3.文法G：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型語言2型語言1型語言0型語言 ( T ) 5.s（rs+s）r=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)*r rr*s(rr*s)*,結(jié)論不成立 三、設文法G的產(chǎn)生式集如下，試給出句子aaabbbccc的至少兩個不同的推導（12分）。 bB→bb CB→BC bC→bc cC→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，如果是，請構(gòu)造出它的有窮描述(FA,RG或者RL）；如果不是，請證明你的結(jié)論（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。 五、構(gòu)造等價于下圖所示DFA的正則表達式。(12分) S q1 q0 q2 q3 1 0 0 0 1 1 1 0 答案(之一)：( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (e+(1+00)((1+00*1)0)*00*) q1 q0 q2 q3 1 0 0 0 1 1 1 0 e e X Y e 預處理： 去掉q3： q1 q0 q2 1 0 1 1+00*1 0 e X Y e 00* 去掉q1： q0 q2 1+00 (1+00*1)0 e X Y e 00* (1+00*1)1 01 q0 e X Y e+(1+00)((1+00*1)0)*00* 01+(1+00)((1+00*1)0)*((1+00*1)1) 去掉q2： 去掉q0： X Y (01+(1+00)((1+00*1)0)*((1+00*1)1))* (e+(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的變化。（10分） 解：處理輸入串00001000的過程中經(jīng)歷的ID變化序列如下： 00001000 00001000 00001000 00001000 000010000 000010000 00001000 00001000 00001000 00001000B 處理輸入串10000的過程中經(jīng)歷的ID變化序列如下： 10000 100000 10000 10000 10000 10000 10000B 七、根據(jù)給定的NFA，構(gòu)造與之等價的DFA。（14分） NFA M的狀態(tài)轉(zhuǎn)移函數(shù)如下表 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(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) 輸入字符 0 1 2 開始狀態(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、設，構(gòu)造下列語言的文法。 (1) 。 解答：。 (2) 。 解答：。 (3) 。 解答： S →aAB|aSAB BA→AB aB→ab bB→bb bA→ba aA→aa (4) 。 解答：。 (5) 。 解答：。 (6) 。 解答： 。 (7) 。 解答：。 (8) 。 解答： 。 2、給定RG：，，試分別構(gòu)造滿足下列要求的RG G，并證明你的結(jié)論。 解： P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1} 證明略。 解： P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1} 證明略。 3、設文法G有如下產(chǎn)生式： S→aB│bA A→a│aS│bAA B→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│bA A→a│aS│SA B→b│bS│SB 進一步地，可以把產(chǎn)生式A→aS中的S代換，把文法化為如下的形式： S→aB│bA A→a│aaB│abA│SA B→b│baB│bbA│SB 7．設DFA M=，證明：對于 注：采用歸納證明的思路 證明： (周期律02282067) 首先對y歸納，對任意x來說，|y| = 0時，即y= 根據(jù)DFA定義,故原式成立。 當|y| = n時，假設原式成立，故當|y|= n+1時， 不妨設y = wa, |w| = n, |a| = 1 根據(jù)DFA定義，故 原式成立， 同理可證，對任意的y來說，結(jié)論也是成立的。 綜上所述，原式得證 ******************************************************************************* 8．證明:對于任意的DFA M1=(Q,Σ,δ,q0,F1) 存在DFA M2=(Q,Σ,δ,q0,F2), 使得L(M2)=Σ*—L（M1）。 證明：（1）構(gòu)造M2。 設DFA M1=(Q,Σ,δ,q0,F1) 取DFA M2=(Q,Σ,δ,q0,Q—F1) （2）證明L(M2)=Σ*—L（M1） 對任意xΣ* x L(M2)=Σ*—L（M1）δ(q,x)Q—F1δ（q,x）Q并且δ（q,x）F1xΣ*并且xL(M1)xΣ*—L（M1） 10、構(gòu)造識別下列語言的NFA 11. 根據(jù)給定的NFA，構(gòu)造與之等價的DFA. （1） NFA M1 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(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) 輸入字符 0 1 2 開始狀態(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等價的DFA 13．試給出一個構(gòu)造方法，對于任意的NFA ，構(gòu)造NFA ，使得 注：轉(zhuǎn)化成相應的DFA進行處理，然后可參考第8題的思路 證明： 首先構(gòu)造一個與NFA 等價的DFA ，根據(jù)定理3.1（P106）， 構(gòu)造其中 在此基礎上， 即取所有確定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。 為了證明，我們在的基礎上，其中，即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然 則又因為故，故 同理容易證明 故，又因為，故 可知，構(gòu)造的是符合要求的。 15． P129 15.(1)、（2） （1）根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù)，起始狀態(tài)q0的e閉包為 e-CLOSURE（q0）={ q0, q2}。由此對以后每輸入一個字符后得到的新狀態(tài)再做e閉包，得到下表： （陶文婧 02282085） 狀態(tài) 0 1 { 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) 0 1 { 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轉(zhuǎn)化的方法來做，而且從e-NFA到NFA轉(zhuǎn)化時狀態(tài)沒有必要改變，可以完全采用e-NFA中的狀態(tài) 如（1） 狀態(tài) 0 1 q0(開始狀態(tài)) { q0, q1，q2 q3} { 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) 0 1 q0(開始狀態(tài)) { q1 q2 q3， } { q0, q1，q2，q3} q1 { q2} { q1，q2} q2 {，q2，q3} { q0, q2，q3} q3（終止狀態(tài)） 空 { q0 } 16、證明對于"的FA M1=(Q1,∑1,δ1,q01,F1)，F(xiàn)A M1=(Q2,∑2,δ2,q02,F2)，存在FA M， 使得 L(M)= L(M1)∪L(M2) 證明：不妨設Q1 與Q2的交集為空 （1） 構(gòu)造M=（Q1∪Q2∪{ q0},∑,δ, q0,F）其中： 1）∑=∑1∪∑2 F= F1∪F2 2) δ(q0,ε)={ q01 ,q02} 對于" q∈Q1,a∈∑1δ(q, a)=δ1(q,a) 對于" q∈Q2,a∈∑2 ,δ(q, a)=δ2(q,a) (1) 證明： 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）∈F F= F1∪F2 則 δ(q01 , x)= δ1(q01 , x)∈F1 因此x∈L(M1) 如果是δ(q02 , x) 因為Q1 與Q2的交集為空 而且δ（q0,x）∈F F= 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} 要證 ， 只需證明 ， 1. 證明 2) 再證明 ******************************************************************************* （吳丹 02282090） 23. FA M的移動函數(shù)定義如下: δ(q0,3)={q0} δ(q0,1)={q1} δ(q1,0)={q2} δ(q1,1)={q3} δ(q2,0)={q2} δ(q3,1)={q3} 其中,q2,q3為終態(tài). (1) M是DFA嗎?為什么? 不是,因為并不是所有的狀態(tài),在接收一個字母表中的字符時會有一個狀態(tài)與之對應. (2) 畫出相應的DFA的狀態(tài)轉(zhuǎn)移圖 (3) 給出你所畫出的DFA的每個狀態(tài)q的set(q):set(q)={x|xΣ*且δ(q0,x)=q} set(q0)={3*} set(q1)={ 3*1} set(q2)={ 3*100*} set(q3)={ 3*111*} set(q)={( 3*0|3*13|3*100*(1|3)|3*111*(0|3)) 0*1*3*} (4) 求正則方法G,使L(G)=L(M) q0→3 q0|1 q1 q1→0 q2|1 q3 q2→0|0 q2 q3→1|1 q3 2.理解如下正則表達式，說明它們表示的語言 （1）(00+11)+表示的語言特征是0和1都各自成對出現(xiàn) （2）(1+0)*0100+表示的語言特征是以010后接連續(xù)的0結(jié)尾 （3）(1+01+001)*(e+0+00) 表示的語言特征是不含連續(xù)的3個0 （4）((0+1)(0+1))*+ ((0+1)(0+1)(0+1))* 表示所有長度為3n或2m的0，1串（n0,m0） （5）((0+1)(0+1))* ((0+1)(0+1)(0+1))* 表示所有長度為3n+2m的0，1串（n0,m0） （6）00+11+（01+10）（00+11）*（10+01）表示的語言特征為長度為偶數(shù)n的串.當n=2時，是00或11的串。n4時，是以01或10開頭，中間的子串00或11成對出現(xiàn)，最后以10或01結(jié)尾的串