是否有工具(或算法)将有限状态机转换为正则表达式？
(反之则不然，那很容易)。
最佳答案
有几种算法可以执行此任务:Brzozowski 和 Mc Cluskey 的“状态消除法”、线性方程组的求解、McNaughton 和 Yamada 的方法等。它们在 Automata and rational expressions 中有很好的描述雅克·萨卡罗维奇 (Jacques Sakarovitch) 着。
特别是状态消除方法很容易理解。关键思想是您将构建一个由有理(也称为正则)表达式而不是字母标记的自动机。首先，确保您有一个初始状态和一个最终状态(如果需要，您可以添加新状态和自发转换)。然后选择一个状态s来消除，比如下图中的状态1。
然后考虑所有对 (p, q)，其中 p 是前任(状态从中转移到 s，图中为 0)，q 是后继(状态 2)。对于每个这样的对 (p, q) 添加一个从 p 到 q 的转换，标记为 E(p, q) + E(p, s)E(s, s)*E(s, q) 其中 E(p , s) 表示“标记从 p 到 s 的转换的表达式。一旦你处理了所有的对 (p, q)，删除状态 s。在前面的例子中:
这样做直到你消除了所有内部状态(即保留初始状态和最终状态)，然后只读取从初始状态到最终状态(这里是 d+ab*c)的转换结果。
您可以使用 Vcsn 来玩弄这个算法，这是一种用于有理表达式和自动机的工具。这是您可以在 Vcsn Sandbox 复制的完整示例。
关于regex - 将有限状态机转换为正则表达式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36853077/