形式語言與自動機(jī)理論試題-資料下載頁
2025-08-05 06:26本頁面
【正文】 同理可證當(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）∈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)與之對應(yīng).(2) 畫出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖(3) 給出你所畫出的DFA的每個狀態(tài)q的set(q):set(q)={x|x206。Σ*且δ(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，說明它們表示的語言（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串（n179。0,m179。0）（5）((0+1)(0+1))* ((0+1)(0+1)(0+1))* 表示所有長度為3n+2m的0，1串（n179。0,m179。0）（6）00+11+（01+10）（00+11）*（10+01）=2時，是00或11的串。n179。4時，是以01或10開頭，中間的子串00或11成對出現(xiàn)，最后以10或01結(jié)尾的串
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1