形式語(yǔ)言與自動(dòng)機(jī)理論試題(參考版)
2024-08-16 06:26本頁(yè)面
【正文】 4時(shí)，是以01或10開頭，中間的子串00或11成對(duì)出現(xiàn)，最后以10或01結(jié)尾的串。0）（6）00+11+（01+10）（00+11）*（10+01）=2時(shí)，是00或11的串。0）（5）((0+1)(0+1))* ((0+1)(0+1)(0+1))* 表示所有長(zhǎng)度為3n+2m的0，1串（n179。Σ*且δ(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，說(shuō)明它們表示的語(yǔ)言（1）(00+11)+表示的語(yǔ)言特征是0和1都各自成對(duì)出現(xiàn)（2）(1+0)*0100+表示的語(yǔ)言特征是以010后接連續(xù)的0結(jié)尾（3）(1+01+001)*(e+0+00) 表示的語(yǔ)言特征是不含連續(xù)的3個(gè)0（4）((0+1)(0+1))*+ ((0+1)(0+1)(0+1))* 表示所有長(zhǎng)度為3n或2m的0，1串（n179。由此對(duì)以后每輸入一個(gè)字符后得到的新?tīng)顟B(tài)再做e閉包，得到下表： （陶文婧 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}，因?yàn)閝3為終止?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}因?yàn)楦鳡顟B(tài)均含有終止?fàn)顟B(tài)，所以q0, q1，q2，q3,q4均為終止?fàn)顟B(tài)注：本題沒(méi)有必要按照NFA到DFA轉(zhuǎn)化的方法來(lái)做，而且從eNFA到NFA轉(zhuǎn)化時(shí)狀態(tài)沒(méi)有必要改變，可以完全采用eNFA中的狀態(tài)如（1）狀態(tài)01q0(開始狀態(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（終止?fàn)顟B(tài)）{ q0, q1，q2，q3}{ q0, q1，q2，q3}(2) 狀態(tài)01q0(開始狀態(tài)){ q1 q2 q3， }{ q0, q1，q2，q3}q1{ q2}{ q1，q2}q2{，q2，q3}{ q0, q2，q3}q3（終止?fàn)顟B(tài)）空{(diào) q0 }1證明對(duì)于的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) 證明：不妨設(shè)Q1 與Q2的交集為空（1） 構(gòu)造M=（Q1∪Q2∪{ q0},∑,δ, q0,F）其中：1）∑=∑1∪∑2 F= F1∪F22) δ(q0,ε)={ q01 ,q02} 對(duì)于 q∈Q1,a∈∑1δ(q, a)=δ1(q,a) 對(duì)于 q∈Q2,a∈∑2 ,δ(q, a)=δ2(q,a)(1) 證明：1）首先證L(M1)∪L(M2)∈L(M
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1