我在这个网站上发现了一个同样的问题，答案是一个描述如何将 NFA 转换为 regex的PDF。但这不起作用，因为此方法有一些条件：
在我的例子中，开始状态只是进入下一个状态，而不是所有状态（例如，q0 进入 q1，但不进入 q2、q3），并且有到开始状态的转换。
那么将 NFA 转换为正则表达式的最简单方法是什么？我没有给出 NFA 示例，因为我没有具体的示例，这只是一个一般性问题，因为我遇到了这种 DFA，其中开始状态未与所有状态连接，并且都转换为开始状态。
我想要一个通用算法来转换这种 NFA。
答案是假设这些条件，因为任何 NFA 都可以修改以满足这些要求。
\n对于任何类型的 NFA，您都可以添加一个新的初始状态 q 0，它具有到原始初始状态的 epsilon 转换，并且还使用名为 \xe2\x88\x85 的附加转换符号（他们称之为空集符号，假设成为与原始 NFA 中的任何符号都不匹配的符号）从它到任何其他状态，然后使用这个新状态作为新的初始状态。请注意，这不会更改原始 NFA 接受的语言。这将使您的 NFA 满足第一个条件。
\n对于任何类型的 NFA，您都可以添加一个新的接受状态 q a，它具有来自原始 NFA 中所有接受状态的 epsilon 转换。然后将此标记为唯一接受状态。请注意，这不会更改原始 NFA 接受的语言。这将使您的 NFA 满足第二个条件。
\n通过上述构造，通过设置q 0 !=q a，满足第三个条件。
\n在您提供的链接中，第四个条件是通过一个名为 \xe2\x88\x85 （空集符号）的特殊转换符号来解释的，原始 NFA 中的实际字母表无法匹配该符号。因此，您可以使用这个新符号添加从每个状态到任何其他状态的转换。请注意，这不会更改原始 NFA 接受的语言。
\n现在 NFA 已被修改以满足四个要求，您可以应用那里的算法将 NFA 转换为正则表达式，它将接受与原始 NFA 相同的语言。
\n编辑以回答进一步的问题：
\n要回答评论中的问题，请考虑具有两个状态 q A和 q B的 NFA 。q A是初始状态，也是唯一的接受状态。我们有一个从 q A到其自身的转换，符号为 0,1。我们还有从 q A到 q B 的转换，符号为 1。最后，我们有从 q B到 q A的转换的转换，符号为 0。
\n可视化：
\n\n 0,1 \n | 1\n->q A ----->q B \n ^ |\n |-------|\n 0\n\n
步骤 2. 当我们标准化 NFA 时，只需放置指向 q A 的新初始状态 (q init )，并放置来自 q A的新接受状态 (q acc ) 。
\n步骤 3. 我们要删除 q A。所以 q A是算法中的q rip （第 3 页）。现在我们需要考虑进入 q A的每个状态和从 q A退出的每个状态。在这种情况下，有两个状态指向 q A，即 q init和 q B。q A指向两个状态，即 q B和 q acc。通过该算法，我们将转移 q 替换为 ->q rip ->q out替换为转换 q in ->q out，转换符号为 R dir +R in (R rip )*R out，其中：
\n所以在这种情况下我们替换转换 q init ->q A ->q q B替换为带有转换符号 (0+1)*1 的q init ->q B。继续这个过程，我们将创建总共 4 个新的转换：
\n然后我们可以删除 q A。
\n步骤 4. 我们要删除 q B。我们再次识别 q in和 q out。这里只有一种状态进入 q B，即 q init，并且只有一种状态离开 q B，即 q acc。所以我们有：
\n所以新的转换 q init ->q acc将是：
\n\n\nR dir +R输入（R rip）*R输出
\n(0+1)* + (0+1)*1 (0(0+1)*1)* 0(0+1)*
\n
我们可以删除 q B。
\n步骤 5. 由于原始 NFA 中的每个状态都已被删除，我们就完成了。所以最终的正则表达式如上所示。
\n请注意，最终的正则表达式可能不是最佳的（并且在大多数情况下它不会是最佳的），这是算法所期望的。一般来说，为 NFA（甚至 DFA）找到最短的正则表达式是非常困难的（尽管在这个例子中很容易看出第一个组件已经涵盖了所有可能的字符串）
\n为了完整起见，接受相同语言的最短正则表达式将是：
\n\n\n(0+1)*
\n