如何从状态图中导出RegEx？

Question

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

我很感激任何帮助，链接，参考和提示！

Answer 1

你在这里正确地得到了正则表达式。你有ab+a+b(a*b)*的表达式等同于(ab+a*)+ab+ - 一旦你完成DFA状态消除（你有一个从开始状态到接受状态的转换），就没有更多的派生要做了。但是，根据您消除状态的顺序，您可能会获得不同的最终正则表达式，并且假设您正确执行了抵销，它们都应该有效。状态消除方法也不能保证能够为特定DFA生成所有等效的正则表达式，因此您没有准确到达原始正则表达式。你也可以check the equivalence of two regular expressions here。

对于您的特定示例，虽然要显示此DFA等同于此原始正则表达式(ab+a*)+ab+，但请查看此消除状态下的DFA（在上面显示的第二步和第三步之间的某处）：

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

然后下一部分(ab+a*)*意味着我们被允许有0或更多的(ab+a*)副本。如果有0个副本，我们将用ab+完成，从a从2到3的过渡的后半部分读取a*a和从3到4过渡的b，使我们进入状态4接受并且在哪里我们可以采取自我循环，并阅读尽可能多的b's我们想要的。

否则我们有一个或多个(ab+a*)副本，再次从a从2到3的过渡的后半部分读取a*a和从3到4过渡的b。 a*来自状态4的a*ab自我循环的前半部分，而下半部分ab要么是正则表达式的最终ab+，要么是另一个(ab+a*)副本的开头。我不确定是否有一个状态消除到达恰好表达式(ab+a*)+ab+但是为了它的价值，我认为你得到的正则表达式更清楚地捕获了这个DFA的结构。