将有限状态机转换为正则表达式 [英] Convert finite state machine to regular expression

问题描述

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

（相反，这很容易。）

解决方案

有几种算法可以执行此任务：来自Brzozowski和Mc Cluskey的消除状态方法，线性方程组的解析度，来自McNaughton和Yamada的方法等。它们在

然后考虑所有对（p，q），其中p是前任（状态从过渡到达s的状态，图中为0）和qa后继（状态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）的转换结果即可。

您可以使用< a href = http://vcsn.lrde.epita.fr rel = noreferrer title = Vcsn> Vcsn ，这是一个用于有理表达式和自动机的工具。下面是一个完整的示例，您可以在

Is there a tool (or an algorithm) to convert a finite state machine into a regular expression?

(not the other way around, that would be easy).

解决方案

There are several algorithms to perform this task: the "state-elimination method" from Brzozowski and Mc Cluskey, the resolution of a system of linear equation, the method from McNaughton and Yamada, etc. They are very well described in Automata and rational expressions by Jacques Sakarovitch.

The state-elimination method in particular is simple to understand. The key idea is that you are going to build an automaton labeled by rational (aka regular) expressions rather than letters. First, make sure you have a single initial state and a single final state (you may add fresh states and spontaneous transitions if necessary). Then choose a state s to eliminate, say state 1 in the following picture.

Then consider all the couples (p, q) where p is a predecessor (states from which a transition reaches s, 0 in the picture) and q a successor (state 2). For each such couple (p, q) add a transition from p to q which is labeled by E(p, q) + E(p, s)E(s, s)*E(s, q) where E(p, s) means "the expression that labels the transition from p to s. Once you treated all the couple (p, q), remove the state s. In the previous example:

Do that until you eliminated all the inner states (i.e., keep the initial state and the final state), and just read the result on the transition from the initial state to the final state (here d+ab*c).

You may toy with this algorithm using Vcsn, a tool for rational expressions and automata. Here is a complete example you may reproduce at Vcsn Sandbox.

这篇关于将有限状态机转换为正则表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！