将有限状态机转换为正则表达式

Question

是否有工具（或算法）可以将有限状态机转换为正则表达式？

（不是反过来，那会很容易）。

Answer 1

您没有具体说明您在做什么，但您可能想知道有一个名为 Ragel 的工具专门用于 FSM。它为多种语言生成代码，几年前我看的时候，将机器移植到其他语言并不难。

Answer 2

您可以使用 fsm2regex，一个可以完成这项工作的在线工具。

Answer 3

我认为我用过的最好的工具是greenery. It is a FSM/regex conversion library for python. You can read more about the library here and the algorithm used is well described here。

例子

可以在网站上找到的模型可以这样转换：

from greenery import fsm, lego

A, B, C, D, E = range(5)
a, b = 'a', 'b'

# create the FSM
machine = fsm.fsm(
    alphabet = {a, b},
    states   = {A, B, C, D, E},
    initial  = A,
    finals   = {C, E},
    map      = {
            A : {a: B, b: D},
            B : {a: C, b: E},
            C : {a: C, b: E},
            D : {a: B, b: D},
            E : {a: B, b: D}
    },
)

# convert it to regex
rex = lego.from_fsm(machine)

输出如下：

>>> print(machine)

  name final? a b
------------------
* 0    False  1 3
  1    False  2 4
  2    True   2 4
  3    False  1 3
  4    True   1 3

>>> print(rex)

b*a((a*(a|b+))?ba)*(a+b?|b)

备注

PYPI上的版本断言有问题，github版本内存有问题，但是组合python 3.x + github版本太棒了。

Answer 4

有几种算法可以执行此任务：来自 Brzozowski 和 Mc Cluskey 的 "state-elimination method"、线性方程组的求解、来自 McNaughton 和 Yamada 的方法等。它们在Automata and rational expressions 作者：雅克·萨卡罗维奇。

尤其是状态消除法，简单易懂。关键思想是您将构建一个由有理（也称为正则）表达式而不是字母标记的自动机。首先，确保您有一个初始状态和一个最终状态（如果需要，您可以添加新状态和自发转换）。然后选择一个状态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, a tool for rational expressions and automata. Here is a complete example you may reproduce at Vcsn Sandbox.

来尝试这个算法

Answer 5

我已经为 http://www.brics.dk/automaton/ Java 包实现了状态消除算法。该实现基于 Sipser, Michael 中说明的算法。计算理论导论。卷。 2. 波士顿：汤姆森课程技术，2006.

您可以在 https://github.com/julianthome/autorex 查看。很乐意得到一些反馈。

将有限状态机转换为正则表达式

Convert finite state machine to regular expression

regex

algorithm

fsm

例子

备注