将正则表达式转换为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更大！