状态消除 DFA 到正则表达式

Question

我有一些关于状态消除和术语的问题。

在上面的示例中，DFA 处于接受状态，必须以符号 0 开始并以 1 结束。

如果我将其转换为正则表达式，则上部将是

底部将是

这是我的问题，我不知道如何将顶部和底部部分添加到单个表达式中。我也不完全确定如何进一步消除 q2 符号 1 。

会是 0(0*(0+1))1* 吗？

感谢任何可以提供帮助的人！

Answer 1

有一种更广为人知且易于理解的算法可用于完成此任务。

要将 DFA G 转换为正则表达式，我们首先将 G 转换为“GNFA”。例如，让 G 为以下 DFA（q 为起始状态）：

将DFA转换为GNFA的过程如下：

1. 添加新的开始状态，并通过 epsilon 转换到原始开始状态。
2. 添加新的接受状态，添加从每个原始接受状态到新添加的接受状态的 epsilon 转换，然后使所有原始接受状态变为正常状态。

这是由此产生的 GNFA：

然后，我们一次删除新的开始状态和新的接受状态之间的每个状态，调整图表以保持正确性。该过程的工作原理如下：令 x、y 和 z 为 DFA 中的状态。此外，转换如下：输入 a 上的 x->y、输入 b 上的 y->y 以及输入 c 上的 y->z。假设我们要删除 y。对于从某个节点 n 到 y 的每个转换以及从 y 到 m 的每个转换，我们必须添加一个新的转换 n->m。从 n 到 m 的转变将是从 n 到 y 转变的内容，后面是带有克林星的转变 y->y 的内容，后面是从 y->m 转变的内容。在这种情况下，a 上的 x->y、b 上的 y->y 和 c 上的 y->z，在删除状态 y 后，将出现从 x->z 上的转换a(b*)c。

考虑图像中的 DFA。删除状态 q 后我们得到：

去掉状态r后，我们得到：

最后，删除 state 后，我们剩下：

这就是我们完整的正则表达式。使用此过程可以完全避免您面临的任何问题。不过，我也会直接回答你的问题。对于初学者来说，上半部分不会是你所建议的。相反，它会变成：这简化为： 这是我们最终的正则表达式，因为底部没有接受状态，因此无关紧要。