將正則表達式轉換爲NFA轉換表

Question

語言無關緊要，但我需要弄清楚如何將正則表達式轉換爲NFA表。 例如「（ab）* + ba」變成
T | a | b |^
0 | N | 1 | 2
1 | 3 | N | N
2 | 4 | N | 3
3 | N | N | N
4 | N | 2 | N

如果有人能幫助我指出正確的方向或告訴我如何做到這一點，將不勝感激。

編輯：我看了看：
http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html，但我仍然無法得到有關如何設定此

Answer 1

首先，找到最外層的操作的想法。在你的例子中，它是+。當你有一個+，這意味着你可以接受左邊的東西或右邊的東西。

Q s Q' 
q0 - M1 
q0 - M2 

我們有q0作爲我們的出發點，我們用M1和M2代表其接受由LHS生成的字符串機和：我們可以使用空（拉姆達，或ε）轉變如下在NFA編碼此RHS分別是我們的正則表達式。當我們說q0轉換爲M1和M2關於lambda/epsilon - 空轉換 - 我們的意思是我們不確定地選擇哪個路徑下降。無論這些狀態如何，轉換將從q0到M1和M2的初始狀態。

現在我們在每個LHS和RHS上遞歸地重複這個過程。我們可以從RHS開始，因爲它更簡單。這裏最外層的操作是連接（符號爲a和b）。級聯是簡單表示：

Q s Q' 
q2 - M3 
M3 - M4 

這裏，q2是M2從之前，和M3和M4初始狀態表示與-的 - 但它接受LHS和RHS分別串接的未確定的機a和b。當我們說q2轉換爲M3時，我們表示它轉換到M3的初始狀態;當我們說M3轉換爲M4時，我們意指所有接受狀態M3轉換到初始狀態M4。

遞歸進行，我們現在需要機器a和b。這些均具有以下形式：

Q s Q' 
q x q' 

凡q是初始狀態，x是符號和q'是接受狀態。所以我們得到：

Q s Q' 
q3 b q4 (q3 initial, q4 accepting) 

和

Q s Q' 
q5 a q6 (q5 initial, q6 accepting) 

我們打這個遞歸分支的底部，可以退一步，開發了基於我們已經定義了具體的機器產生的轉換表的具體條目。我們有這樣的：

Q s Q' 
q2 - M3 
M3 - M4 

現在我們知道什麼是M3和M4的樣子，所以我們可以代替：

Q s Q' 
q2 - q3 
q3 b q4 
q4 - q5 
q5 a q6 (q2 initial, q6 accepting) 

現在我們準備從+操作做LHS。最外面的操作*。我們在NFA中處理這些數據的方式如下：

Q s Q' 
q7 - M5 
M5 - M5 

我們現在考慮下一個操作，連接。我們已經討論過這一點，我們知道我們會得到：

Q s Q' 
q8 - M6 
M6 - M7 

現在我們需要a和b。同樣，我們知道這些看起來像：

Q s Q' 
q9 a q10 

和

Q s Q' 
q11 b q12 

我們把它全部重新走到一起：

Q s Q' 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 (q8 initial, q12 accepting) 

然後我們做了克林星：

Q s Q' 
q7 - q8 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 
q12 - q8 (q8 initial, q8 and q12 accepting) 

最後，我們結合所有的規則，在一個大的反式ition表：

Q s Q' 

q0 - q2 
q0 - q7 

q2 - q3 
q3 b q4 
q4 - q5 
q5 a q6 

q7 - q8 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 
q12 - q8 (q0 initial, q6, q8 and q12 accepting) 

因此，您可以遞歸地爲任何正則表達式構造一個NFA。得到的NFA會有一些不必要的狀態在一般情況下，但NFA優化是一個很微妙的問題。您可以隨時利用這個（或任何）NFA，使用已知的算法轉換爲DFA，然後使用已知的算法最小化。然後，你有可證明的最小的DFA，儘管它可能比連這個填充NFA更大！