将 NFA 转换为正则表达式

我在这个网站上发现了同样的问题，答案是描述如何将 NFA 转换为正则表达式的 PDF http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf。但这是行不通的，因为该方法有一些条件：

1. 存在从初始状态到所有其他状态的转换，并且没有 过渡到初始状态。
2. 有一个接受状态，只有进入它的转换（并且没有传出） 过渡）。
3. 接受状态与初始状态不同。
4. 除了初始状态和接受状态外，所有其他状态都与所有其他状态相连 通过过渡状态。特别是，每个状态都有一个到自身的转换。

在我的示例中，开始状态只是进入下一个状态，而不是所有状态（例如 q0 进入 q1，但不进入 q2、q3），并且存在到开始状态的转换。

那么将 NFA 转换为正则表达式的最简单方法是什么？我没有给出 NFA 的例子，因为我没有具体的例子，这只是一个一般性的问题，因为我遇到过这种 DFA，其中起始状态并不与所有状态相关，并且是转换到启动状态。

我想要一个通用算法来转换这种 NFA。

答案是假设这些条件，因为任何 NFA 都可以修改以满足这些要求。

For any kind of NFA, you can add a new initial state q₀ that has an epsilon-transition to the original initial state, and also using an additional transition symbol called ∅ (they call it empty set symbol, assumed to be a symbol which does not match any symbol from the original NFA) from it to any other states, then use this new state as the new initial state. Note that this does not change the language accepted by the original NFA. This would make your NFA satisfies the first condition.

For any kind of NFA, you can add a new acceptance state q_a that has an epsilon-transition from all acceptance state in the original NFA. Then mark this as the only acceptance state. Note that this does not change the language accepted by the original NFA. This would make your NFA satisfies the second condition.

By the above construction, by setting q₀ != q_a, it satisfies the third condition.

在您提供的链接中，第四个条件是通过一个称为 ∅（空集符号）的特殊转换符号来解释的，原始 NFA 中的实际字母表无法匹配该符号。因此，您可以使用这个新符号添加从每个状态到任何其他状态的转换。请注意，这不会更改原始 NFA 接受的语言。

现在 NFA 已被修改以满足四个要求，您可以应用那里的算法将 NFA 转换为正则表达式，它将接受与原始 NFA 相同的语言。

编辑以回答进一步的问题:

To answer your question in the comment, consider the NFA with two states, q_A and q_B. q_A is the initial state as well as the only acceptance state. We have a transition from q_A to itself with symbol 0,1. We also have transition from q_A to q_B with symbol 1. Lastly we have transition from q_B to q_A with symbol 0.

可视化：

 0,1    
  |  1
->qA----->qB
  ^       |
  |-------|
     0
  

Step 2. When we normalize the NFA, just put the new init state (q_init) that points to q_A, and put a new acceptance state (q_acc) from q_A.

Step 3. We want to remove q_A. So q_A is the q_rip in the algorithm (in page 3). Now we need to consider every states that enters q_A and every states that exits from q_A. In this case, there are two states pointing to q_A, that are q_init and q_B. There are two states that are pointed to by q_A, that are q_B and q_acc. By the algorithm, we replace the transitions q_in->q_rip->q_out with a transition q_in->q_out, having the transition symbol R_dir+R_in(R_rip)*R_out, where:

1. R_dir is the original transition from q_in to q_out
2. R_in is the original transition from q_in to q_rip
3. R_rip is the original loop at q_rip
4. R_out is the original transition from q_rip to q_out

So in this case we replace the transition q_init->q_A->q_B with q_init->q_B with transition symbol (0+1)*1. Continuing this process, we will create in total 4 new transitions:

1. q_init->q_B: (0+1)*1
2. q_init->q_acc: (0+1)*
3. q_B->q_B: 0(0+1)*1
4. q_B->q_acc: 0(0+1)*

Then we can remove q_A.

Step 4. We want to remove q_B. Again, we identify the q_in and q_out. There is only one state coming to q_B here, which is q_init, and there is only one state departing from q_B, which is q_acc. So we have:

1. R_dir = (0+1)*
2. R_in = (0+1)*1
3. R_rip = 0(0+1)*1
4. R_out = 0(0+1)*

So the new transition q_init->q_acc will be:

R_dir+R_in(R_rip)*R_out

(0+1)* + (0+1)*1 (0(0+1)*1)* 0(0+1)*

And we can remove q_B.

步骤 5. 由于原始 NFA 中的每个状态都已被删除，我们就完成了。所以最终的正则表达式如上所示。

请注意，最终的正则表达式可能不是最佳的（并且在大多数情况下它不会是最佳的），这是算法所期望的。一般来说，为 NFA（甚至 DFA）找到最短的正则表达式是非常困难的（尽管在这个例子中很容易看出第一个组件已经涵盖了所有可能的字符串）

为了完整起见，接受相同语言的最短正则表达式将是：

(0+1)*