regex - 状态消除 DFA 到正则表达式

Question

我有几个关于状态消除和术语的问题。

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

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

底部是

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

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

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

标签： regexregular-languagefinite-automatadfa

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 的过渡的内容，然后是带有 kleene 星的过渡 y->y 的内容，然后是从 y->m 的过渡的内容。在这种情况下，a 上的 x->y，b 上的 y->y 和 c 上的 y->z，在移除状态 y 之后，将有一个从 x->z on 的转换a(b*)c。

---

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

移除状态 r 后，我们得到：

最后，在移除 state 之后，我们剩下：

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