将正则表达式转换为 NFA 转换 table
Converting regex to a NFA transistion table
语言无关紧要，但我需要弄清楚如何将正则表达式转换为 NFA table。
例如“(ab)* + ba”变成
吨 |一个 |乙 | ^
0 |否 | 1 | 2
1 | 3 |否 | N
2 | 4 |否 | 3
3 |否 |否 | N
4 |否 | 2 | N
如果有人能帮助我指出正确的方向或告诉我如何做到这一点，我们将不胜感激。
编辑：我看了一下：
http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html，但我仍然无法了解如何对此进行编程
首先，找到最外层的操作。在您的示例中，它是 +。当你有一个 + 时，这意味着你可以接受左边的东西或右边的东西。我们可以使用空（lambda 或 epsilon）转换在 NFA 中对其进行编码，如下所示：
Q s Q'
q0 - M1
q0 - M2
我们以 q0 作为起点，我们使用 M1 和 M2 来表示接受分别由正则表达式的 LHS 和 RHS 生成的字符串的机器。当我们说 q0 在 lambda/epsilon 上过渡到 M1 和 M2 - 空过渡 - 我们的意思是我们不确定地选择要走的路径。过渡将从 q0 到 M1 和 M2 的初始状态，无论这些状态是什么。
现在我们在每个左轴和右轴上递归地重复该过程。我们可以从 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)
我们已经触及此递归分支的底部，并且可以返回，根据我们定义的具体机器在转换 table 中生成具体条目。我们有这个：
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)
最后，我们将所有规则合并为一个大转换table:
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 大得多！
语言无关紧要，但我需要弄清楚如何将正则表达式转换为 NFA table。
例如“(ab)* + ba”变成
吨 |一个 |乙 | ^
0 |否 | 1 | 2
1 | 3 |否 | N
2 | 4 |否 | 3
3 |否 |否 | N
4 |否 | 2 | N
如果有人能帮助我指出正确的方向或告诉我如何做到这一点，我们将不胜感激。
编辑：我看了一下：
http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html，但我仍然无法了解如何对此进行编程
首先，找到最外层的操作。在您的示例中，它是 +。当你有一个 + 时，这意味着你可以接受左边的东西或右边的东西。我们可以使用空（lambda 或 epsilon）转换在 NFA 中对其进行编码，如下所示：
Q s Q'
q0 - M1
q0 - M2
我们以 q0 作为起点，我们使用 M1 和 M2 来表示接受分别由正则表达式的 LHS 和 RHS 生成的字符串的机器。当我们说 q0 在 lambda/epsilon 上过渡到 M1 和 M2 - 空过渡 - 我们的意思是我们不确定地选择要走的路径。过渡将从 q0 到 M1 和 M2 的初始状态，无论这些状态是什么。
现在我们在每个左轴和右轴上递归地重复该过程。我们可以从 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)
我们已经触及此递归分支的底部，并且可以返回，根据我们定义的具体机器在转换 table 中生成具体条目。我们有这个：
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)
最后，我们将所有规则合并为一个大转换table:
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 大得多！