如何从状态图中推导出RegEx？
How to derive the RegEx from the state diagram?
我在脚本中找到了 DFA（确定性有限自动机）及其正则表达式的状态图，但该图只是一个示例，没有任何解释。于是尝试自己从DFA状态图中推导出RegEx，得到表达式：ab+a+b(a*b)*。我不明白我是如何得到脚本中提到的原始 RegEx (ab+a*)+ab+ 的。这是我的推导：
非常感谢任何帮助、链接、参考和提示！
您在这里正确地导出了正则表达式。你的表达式 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*a 从 2 到 3 的过渡的后半部分读取 a 和从 b 3 到 4 的过渡，使我们进入状态 4，这是接受状态，我们可以在其中进行自循环并读取任意数量的 b。
否则我们有 1 个或多个 (ab+a*) 副本，再次读取 a*a 从 2 到 3 的后半部分的 a 和 b从3到4过渡。 a* 来自状态 4 上 a*ab 自循环的前半部分，后半部分 ab 是正则表达式的最后 ab+ 或另一个副本的开始(ab+a*) 个。我不确定是否有一个状态消除可以精确地到达表达式 (ab+a*)+ab+ 但对于它的价值，我认为你派生的正则表达式更清楚地捕捉了这个 DFA 的结构。
我在脚本中找到了 DFA（确定性有限自动机）及其正则表达式的状态图，但该图只是一个示例，没有任何解释。于是尝试自己从DFA状态图中推导出RegEx，得到表达式：ab+a+b(a*b)*。我不明白我是如何得到脚本中提到的原始 RegEx (ab+a*)+ab+ 的。这是我的推导：
非常感谢任何帮助、链接、参考和提示！
您在这里正确地导出了正则表达式。你的表达式 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*a 从 2 到 3 的过渡的后半部分读取 a 和从 b 3 到 4 的过渡，使我们进入状态 4，这是接受状态，我们可以在其中进行自循环并读取任意数量的 b。
否则我们有 1 个或多个 (ab+a*) 副本，再次读取 a*a 从 2 到 3 的后半部分的 a 和 b从3到4过渡。 a* 来自状态 4 上 a*ab 自循环的前半部分，后半部分 ab 是正则表达式的最后 ab+ 或另一个副本的开始(ab+a*) 个。我不确定是否有一个状态消除可以精确地到达表达式 (ab+a*)+ab+ 但对于它的价值，我认为你派生的正则表达式更清楚地捕捉了这个 DFA 的结构。