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

EN

完成这一任务的算法有几种: Brzozowski和Mc Cluskey的“状态消除法”、线性方程组的分辨率、McNaughton和Yamada的方法等，这些算法在雅克·萨卡洛维奇的“自动机与有理表达式”中有很好的描述。

尤其是状态消除方法，很容易理解。关键的想法是，您将构建一个由rational (也称为正则)表达式而不是字母标记的自动机。首先，确保您有一个初始状态和一个最终状态(如果需要，您可以添加新的状态和自发的转换)。然后选择要消除的状态，例如下图中的状态1。

​

​

然后考虑所有的配对(p，q)，其中p是一个前驱体(图中的过渡达到s，0的状态)和q是一个继承者(状态2)。对每对这样的夫妇(p，q)加一个从p到q的过渡，它由E(p，q) + E(p，s)E( s，s)*E( s，s)标记为E(s，s)*E(s，s)，其中E(p，s)的意思是“标记从p到s的过渡的表达式。一旦你处理了所有的夫妻(p，q)，移除状态s。在前面的例子中：

​

​

这样做，直到消除了所有内部状态(即保留初始状态和最终状态)，并读取从初始状态到最终状态的转换结果(此处为d+ab*c)。

您可以使用Vcsn来玩这个算法，这是一个用于rational表达式和自动机的工具。下面是一个完整的示例，您可以在Vcsn砂箱上进行复制。

​

​

我相信我使用过的最好的工具是greenery。它是用于python的FSM/regex转换库。您可以阅读更多关于库这里的信息，所使用的算法是很好描述的这里。

示例

​

​

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

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版本在内存方面也有一些问题，但是Python3.x+ github版本的组合非常棒。

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