正規(guī)文法與有限自動機的相互轉換-文庫吧資料
2025-07-02 14:38本頁面
【正文】 _midd_stat。 cin stat[0]。 char* stat = new char[n]。 //n_midd_stat為中間狀態(tài)的數目 //n_final_stat為終態(tài)的數目 cout 請輸入自動機共有的狀態(tài)數目：。int main(){ int n, m。從有限自動機M=( S，∑，d，S0，F)構造左線性正規(guī)文法GL的方法如下：令GL=(∑,S, X，P)，其中P是由以下規(guī)則定義的產生式集合：對任何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→ε。 有限自動機到正規(guī)文法的構造方法上述定理的證明采用了構造性的證明方法，由此可以得出由有限自動機到正規(guī)文法的構造方法。（2）若S0 F，則ε L(M)，但上面構造的L(GL)中不含ε。反之亦然。2. 設DFAM=(S，∑，d，S0，F)，分以下兩種情況進行證明：（1）若S0 F，則令GL=(∑,S, X, P)，其中X F，P是由以下規(guī)則定義的產生式集合，對任何a ∑及A,B S，若d(A，a)=B，則：①當A≠S0時，令B→Aa；②當A=S0時，令B→a∣Aa；顯然，上述得到的文法為一個左線性正規(guī)文法，下面說明它們的等價性(L(M)=L(GL) )。（2）若S0 F，因為d(S0,ε)= S0，所以ε L(M)，但上面構造的L(GR)中不含ε。反之亦然。證明：=(S，∑，d，S0，F)，分以下兩種情況進行證明：（1）若S0 F，則令GR=(∑,S, S0, P)，其中P是由以下規(guī)則定義的產生式集合，對任何a ∑及A,B S，若d(A，a)=B，則：①當B F時，令A→aB；②當B F時，令A→aB∣a；顯然，上述得到的文法為一個右線性正規(guī)文法，下面說明它們的等價性(L(M)=L(GR) )。從左線性正規(guī)文法GL=(VT,VN,S,P)構造有限自動機M=( VN {q}，VT，d，q，{S})的方法如下：①將VN中每個符號視為一個狀態(tài)符號，增加一個新的初態(tài)符號q，q VN；②對于產生式A→a（a VT {ε}），則構造d(q，a)=A；③對于產生式A1→Aa（a VT {ε}），則構造d(A，a)= A1。 正規(guī)文法到有限自動機的構造方法上述定理的證明采用了構造性的證明方法，由此可以得出由正規(guī)文法到有限自動機的構造方法。在推導的最后，利用A→a一次則相當于在Ｍ中從狀態(tài)q出發(fā)經標記為a的箭弧到達狀態(tài)A(包括a=ε的情形)。到此，已說明存在一個FAM與該左線性文法對應，下面說明它們的等價性(L(GL)=L(M) )。令M=(VN {q}，VT，d，q，{S})，其中狀態(tài)轉換函數d由以下規(guī)則定義：①若對某個A VN及a VT {ε}，P中有產生式A→a，則令d(q，a)=A；②對任意的A VN及a VT {ε}，設P中所有右端第一個符號為A，第二個符號為a的所有產生式為A1→Aa，A2→Aa，…，AK→Aa，則令d(A，a)={ A1，A2，…，Ak}。綜上所述，在正規(guī)文法GR中，S W的充要條件是：在M中，從狀態(tài)S到狀態(tài)f有一條通路，其上所有箭弧的標記符號依次連接起來恰好等于W，這就是說，W L(GR)當且僅當W L(M)，故L(GR)=L(M)。對右線性正規(guī)文法GR，在S W的最左推導過程中，利用A→aB一次就相當于在M中從狀態(tài)A出發(fā)經標記為a的箭弧到達狀態(tài)B(包括a=ε的情形)。顯然上述得到的M為一個NFA。證明：=（VT,VN,S,P），將VN中每個非終結符視為狀態(tài)符號，并增加一個新的終止符號f，（f VN）。而這些數據可以用哪種正規(guī)式概括進來。任意的正規(guī)式都可以轉
環(huán)評公示相關推薦
鄂ICP備17016276號-1