regex - 如何从状态图中导出 RegEx？

Question

我在脚本中找到了带有 RegEx 的 DFA（确定性有限自动机）的状态图，但该图只是一个示例，没有任何解释。于是我自己尝试从DFA状态图中推导出RegEx，得到表达式：ab+a+b(a*b)*. 我不明白如何获得(ab+a*)+ab+脚本中提到的原始 RegEx。这是我的推导：

我感谢任何帮助、链接、参考和提示！

Answer 1

您在此处正确导出了正则表达式。您拥有的表达式ab+a+b(a*b)*等同于(ab+a*)+ab+- 一旦您完成了 DFA 状态消除（您有一个从开始状态到接受状态的单一转换），就没有更多的推导可做。但是，根据消除状态的顺序，您可能会得到不同的最终正则表达式，并且假设您正确地进行了消除，它们都应该是有效的。状态消除方法也不能保证能够为特定的 DFA 生成所有等效的正则表达式，因此您没有得到完全原始的正则表达式是可以的。您还可以在此处检查两个正则表达式的等价性。

对于您的特定示例，尽管要显示此 DFA 等效于此原始 regex (ab+a*)+ab+，但请查看处于消除状态的 DFA（在上面显示的第二步和第三步之间的某个位置）：

让我们将表达式扩展(ab+a*)+ab+为(ab+a*)(ab+a*)*ab+。所以在 DFA 中，第一个(ab+a*)让我们从状态 0 到状态 2 和 3 之间（a*in a*a）。

然后下一部分(ab+a*)*意味着我们可以拥有 0 个或多个(ab+a*). 如果有 0 个副本，我们将完成一个，从从 2 到 3的转换的后半部分ab+读取 an和从 3 到 4 转换的 a ，使我们进入状态 4，它正在接受并且我们可以采取自循环并读取任意数量的 's。aa*abb

否则，我们有 1 个或多个副本，再次从 2 到 3的过渡的后半部分(ab+a*)读取 an ，从 3 到 4 的过渡读取 a 。来自状态 4 上自循环的前半部分，后半部分是正则表达式的最后部分或. 我不确定是否存在完全达到表达式的状态消除，但对于它的价值，我认为您派生的正则表达式更清楚地捕捉了这个 DFA 的结构。aa*aba*a*ababab+(ab+a*)(ab+a*)+ab+