形式語言與自動機理論試題(編輯修改稿)
2025-09-01 06:26 本頁面
【文章內(nèi)容簡介】 。 (7) 。 解答：。 (8) 。 解答： 。給定RG：，試分別構(gòu)造滿足下列要求的RG G，并證明你的結(jié)論。解：P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1}證明略。解：P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1}證明略。設(shè)文法G有如下產(chǎn)生式： S→aB│bAA→a│aS│bAAB→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│bAA→a│aS│SAB→b│bS│SB進一步地，可以把產(chǎn)生式A→aS中的S代換，把文法化為如下的形式： S→aB│bAA→a│aaB│abA│SAB→b│baB│bbA│SB7．設(shè)DFA M=，證明：對于注：采用歸納證明的思路證明： (周期律02282067)首先對y歸納，對任意x來說，|y| = 0時，即y=根據(jù)DFA定義,故原式成立。當|y| = n時，假設(shè)原式成立，故當|y|= n+1時，不妨設(shè)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。 設(shè)DFA M1=(Q,Σ,δ,q0,F1) 取DFA M2=(Q,Σ,δ,q0,Q—F1) （2）證明L(M2)=Σ*—L（M1） 對任意x206。Σ*x206。 L(M2)=Σ*—L（M1）219。δ(q,x)206。Q—F1219。δ（q,x）206。Q并且δ（q,x）207。F1219。x206。Σ*并且x207。L(M1)219。x206。Σ*—L（M1）構(gòu)造識別下列語言的NFA 11. 根據(jù)給定的NFA，構(gòu)造與之等價的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}終止狀態(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
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1