正規(guī)文法與有限自動(dòng)機(jī)的相互轉(zhuǎn)換(編輯修改稿)
2025-07-23 14:38 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 {ε}），則構(gòu)造d(q，a)=A；③對(duì)于產(chǎn)生式A1→Aa（a VT {ε}），則構(gòu)造d(A，a)= A1。 有限自動(dòng)機(jī)到正規(guī)文法的等價(jià)性證明定理2：對(duì)于每一個(gè)有限自動(dòng)機(jī)M，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL與之等價(jià)。證明：=(S，∑，d，S0，F(xiàn))，分以下兩種情況進(jìn)行證明：（1）若S0 F，則令GR=(∑,S, S0, P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合，對(duì)任何a ∑及A,B S，若d(A，a)=B，則：①當(dāng)B F時(shí)，令A(yù)→aB；②當(dāng)B F時(shí)，令A(yù)→aB∣a；顯然，上述得到的文法為一個(gè)右線性正規(guī)文法，下面說(shuō)明它們的等價(jià)性(L(M)=L(GR) )。在DFAM中，對(duì)任何w ∑*，不妨設(shè)w=a1a2…ak，其中ai ∑(i=1,2,…,k)，若S W，則存在一個(gè)最左推導(dǎo)：S0 a1A1 a1a2A2 … a1…aiAi a1…aiai+1Ai+1 … a1…ak，因而，在M中存在一條從S0出發(fā)一次經(jīng)過(guò)A1，…，Ak1到達(dá)終態(tài)的通路，該通路上所有箭弧的標(biāo)記依次為a1，…，ak。反之亦然。所以，w L(GR)當(dāng)且僅當(dāng)w L(M)，故L(M)=L(GR)。（2）若S0 F，因?yàn)閐(S0,ε)= S0，所以ε L(M)，但上面構(gòu)造的L(GR)中不含ε。因此，需在文法中添加產(chǎn)生式S0→ε，這樣，就有L(M)=L(GR)。2. 設(shè)DFAM=(S，∑，d，S0，F(xiàn))，分以下兩種情況進(jìn)行證明：（1）若S0 F，則令GL=(∑,S, X, P)，其中X F，P是由以下規(guī)則定義的產(chǎn)生式集合，對(duì)任何a ∑及A,B S，若d(A，a)=B，則：①當(dāng)A≠S0時(shí)，令B→Aa；②當(dāng)A=S0時(shí)，令B→a∣Aa；顯然，上述得到的文法為一個(gè)左線性正規(guī)文法，下面說(shuō)明它們的等價(jià)性(L(M)=L(GL) )。在DFAM中，對(duì)任何w ∑*，不妨設(shè)w=a1a2…ak，其中ai ∑(i=1,2,…,k)，若存在一條從S0到X的通路，通路上所有箭弧的標(biāo)記依次為a1，…，ak，則在GL中一定存在一個(gè)最左推導(dǎo)：X Akak Ak1ak1ak … A2a2…ak … a1…ak，即w L(GL)。反之亦然。所以，w L(GL)當(dāng)且僅當(dāng)w L(M)，故L(M)=L(GL)。（2）若S0 F，則ε L(M)，但上面構(gòu)造的L(GL)中不含ε。因此，需在文法中添加產(chǎn)生式X→ε，這樣，就有L(M)=L(GL)。 有限自動(dòng)機(jī)到正規(guī)文法的構(gòu)造方法上述定理的證明采用了構(gòu)造性的證明方法，由此可以得出由有限自動(dòng)機(jī)到正規(guī)文法的構(gòu)造方法。從有限自動(dòng)機(jī)M=( S，∑，d，S0，F(xiàn))構(gòu)造右線性正規(guī)文法GR的方法如下：令GR=(∑,S, S0，P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對(duì)任何d(A，a)=B,①若B F，則令A(yù)→aB；②若B F，并且B狀態(tài)有箭弧射出，則令A(yù)→aB∣a；若B F，并且B狀態(tài)沒(méi)有箭弧射出，則令A(yù)→a；③若S0 F，則令S0→ε。從有限自動(dòng)機(jī)M=( S，∑，d，S0，F(xiàn))構(gòu)造左線性正規(guī)文法GL的方法如下：令GL=(∑,S, X，P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對(duì)任何d(A，a)=B,①若A不是初始狀態(tài)，則令B→Aa；②若A是初始狀態(tài)，并且A狀態(tài)有箭弧射入，則令B→Aa∣a；若A是初始狀態(tài)，并且A狀態(tài)沒(méi)有箭弧射入，則令B→a；③若S0 F，則令X→ε。4代碼編寫(xiě)includeiostreamusing namespace std。int main(){ int n, m。 //n為自動(dòng)機(jī)狀態(tài)的總數(shù)目 //m為自動(dòng)機(jī)終結(jié)符的數(shù)目 int n_midd_stat, n_final_stat。 //n_midd_stat為中間狀態(tài)的數(shù)目 //n_final_stat為終態(tài)的數(shù)目 cout 請(qǐng)輸入自動(dòng)機(jī)共
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1