形式語(yǔ)言與自動(dòng)機(jī)理論試題-文庫(kù)吧資料
2024-08-18 06:26本頁(yè)面
【正文】 )設(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）∈F F= F1∪F2 則δ(q01 , x)= δ1(q01 , x)∈F1 因此x∈L(M1)如果是δ(q02 , x) 因?yàn)镼1 與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 證明：對(duì)于任意的FA . 證明：令 ,其中δ的定義為： 1) 對(duì)q∈Q1{f1}，a∈∑∪{ε} δ(q，a)=δ1(q，a)； 2) 顯然則又因?yàn)楣?，故同理容易證明故，又因?yàn)?，故可知，?gòu)造的是符合要求的。Σ*—L（M1）構(gòu)造識(shí)別下列語(yǔ)言的NFA 11. 根據(jù)給定的NFA，構(gòu)造與之等價(jià)的DFA. （1） NFA M1 的狀態(tài)轉(zhuǎn)移函數(shù)如表39狀態(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]圖39所示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 ，（P106）， 構(gòu)造其中 在此基礎(chǔ)上，即取所有確定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。L(M1)219。x206。Q并且δ（q,x）207。Q—F1219。 L(M2)=Σ*—L（M1）219。 設(shè)DFA M1=(Q,Σ,δ,q0,F1) 取DFA M2=(Q,Σ,δ,q0,Q—F1) （2）證明L(M2)=Σ*—L（M1） 對(duì)任意x206。綜上所述，原式得證*
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1