regex - 将 NFA 转换为正则表达式

Question

我在这个网站上发现了同样的问题，答案是PDF describing how to convert an NFA to a regex .但这不起作用，因为此方法有一些条件:

有从初始状态到所有其他状态的转换，并且没有
过渡到初始状态。

有一个接受状态，只有进入它的转换(没有传出
过渡)。

接受状态不同于初始状态。

除了初始状态和接受状态外，所有其他状态都连接到所有其他状态
状态通过过渡。特别是，每个状态都有一个到它自己的转换。

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

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

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

Answer 1

答案是假设这些条件，因为可以修改任何 NFA 以满足这些要求。
对于任何类型的 NFA，您都可以添加一个新的初始状态 q0，它具有到原始初始状态的 epsilon 转换，并且还可以使用一个名为 ∅ 的附加转换符号(他们称之为空集符号，假设是一个符号不匹配来自原始 NFA 的任何符号)从它到任何其他状态，然后使用这个新状态作为新的初始状态。请注意，这不会更改原始 NFA 接受的语言。这将使您的 NFA 满足第一个条件。
对于任何类型的 NFA，您都可以添加一个新的接受状态 qa，它具有来自原始 NFA 中所有接受状态的 epsilon 转换。然后将此标记为唯一接受状态。请注意，这不会更改原始 NFA 接受的语言。这将使您的 NFA 满足第二个条件。
通过上面的构造，通过设置q0 != qa，它满足第三个条件。
在您提供的链接中，第四个条件是通过一个称为 ∅(空集符号)的特殊转换符号来解释的，原始 NFA 中的实际字母表无法与之匹配。因此，您可以使用这个新符号添加从每个状态到任何其他状态的转换。请注意，这不会更改原始 NFA 接受的语言。
所以现在NFA已经被修改为满足这四个要求，你可以在那里应用算法将NFA转换为正则表达式，它会接受与原始NFA相同的语言。
编辑以回答进一步的问题:
要在评论中回答您的问题，请考虑具有两个状态 qA 和 qB 的 NFA。 qA 是初始状态，也是唯一的接受状态。我们有一个从 qA 到它自身的转换，符号为 0,1。我们也有从 qA 到 qB 的转换，符号为 1。最后我们有从 qB 到 qA 的转换，符号为 0。
可视化:
0,1
| 1
->qA----->qB
^ |
|-------|
0

Step 2. 当我们对 NFA 进行归一化时，只需放入指向 qA 的新 init 状态(qinit)，并放入来自 qA 的新接受状态(qacc)。
第 3 步。我们要删除 qA。所以 qA 是算法中的 qrip(第 3 页)。现在我们需要考虑每个进入 qA 的状态和每个退出 qA 的状态。在这种情况下，有两个状态指向 qA，即 qinit 和 qB。 qA 指向两个状态，即 qB 和 qacc。通过该算法，我们将转换 qin->qrip->qout 替换为转换 qin->qout，转换符号为 Rdir+Rin(Rrip)*Rout，其中:

rdir是qin到qout的原始过渡

Rin是从qin到qrip的原始过渡

Rrip 是 qrip 的原始循环

Rout 是从 qrip 到 qout 的原始过渡

因此，在这种情况下，我们将 qinit->qA->qB 替换为 qinit->qB 转换符号 (0+1)*1。继续这个过程，我们将总共创建 4 个新的过渡:

qinit->qB: (0+1)*1

qinit->qacc: (0+1)*

qB->qB: 0(0+1)*1

qB->qacc: 0(0+1)*

然后我们可以删除qA。
第 4 步。我们要删除 qB。再次，我们识别 qin 和 qout。这里进入qB的状态只有一种，就是qinit，离开qB的状态也只有一种，就是qacc。所以我们有:

Rdir = (0+1)*

凛 = (0+1)*1

Rrip = 0(0+1)*1

溃败 = 0(0+1)*

所以新的转换 qinit->qacc 将是:

R_dir+R_in(R_rip)*R_out

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

我们可以删除qB。
步骤 5. 由于原始 NFA 中的每个状态都已被删除，我们就完成了。所以最终的正则表达式如上所示。
请注意，最终的正则表达式可能不是最佳的(并且在大多数情况下它不会是最佳的)，这是算法所预期的。一般来说，为 NFA(甚至 DFA)找到最短的正则表达式是非常困难的(尽管在这个例子中很容易看出第一个组件已经涵盖了所有可能的字符串)
为完整起见，接受相同语言的最短正则表达式为:

(0+1)*