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

有几种算法可以执行这项任务：Brzozowski和Mc Cluskey的“状态消除方法”,线性方程组的解析,McNaughton和Yamada的方法等.他们在 Automata and rational expressions由Jacques Sakarovitch很好地描述.

特别是状态消除方法很容易理解.关键的想法是你要构建一个由理性(也就是常规)表达而不是字母标记的自动机.首先,确保您有一个初始状态和一个最终状态(如果需要,您可以添加新状态和自发转换).然后选择要消除的状态s,如下图所示的状态1.

然后考虑所有的对(p,q),其中p是前趋(转换到s的状态,图中的0)和q后继(状态2).对于每个这样的对(p,添加从p到q的转变,其由E(p,q)标记E(p,s)E(s,s)* E(s,q)其中E(p,s)表示“标记从p到s的转换的表达式.一旦你处理了所有的对(p,删除状态s.在前面的例子中：

这样做直到你消除所有内部状态(即保持初始状态和最终状态),然后只读取从初始状态到最终状态(这里是d ab * c)的转换结果.

你可以使用Vcsn来玩这个算法,这是一个理性表达和自动机的工具.以下是您可以在Vcsn Sandbox重现的完整示例.