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