Convert a state machine to a regular expression

Question

Is there a tool (or algorithm) for converting a finite state machine into a regular expression?

(not vice versa, that would be easy).

Answer 1

There are several algorithms for performing this task: the “method of eliminating states” from Brzozowski and Mac Klaski, resolving the linear equation system, the Macnaughton and Yamada method, etc. They are very well described in Automatons and rational expressions of Jacques Sakarovich.

The method of eliminating states in particular is easy to understand. The basic idea is that you are going to create an automaton marked with rational (aka regular) expressions, not letters. First, make sure that you have one initial state and one final state (if necessary, you can add new states and spontaneous transitions). Then select state s to eliminate, say, state 1 in the following figure.

Then we consider all pairs (p, q), where p is the predecessor (states from which the transition reaches s, 0 in the figure) and q is the successor (state 2). For each such pair (p, q), add the transition from p to q, which is labeled E (p, q) + E (p, s) E (s, s) * E (s, q), where E (p, s) means "expression that indicates the transition from p to S. After you have processed all the pairs (p, q), delete the state s. In the previous example:

Do this until you eliminate all the internal states (i.e., save the initial state and final state), and simply read the result when switching from the initial state to the final state (here d + ab * c).

You can play with this algorithm using Vcsn , a tool for rational expressions and automata. Here is a complete example that you can reproduce on Vcsn Sandbox .

Answer 2

You will not indicate what you are doing, but you may know that there is a tool called Ragel that specializes in Finite State Machines. It generates code for many languages, and when I looked a few years ago, it wasn’t so difficult to port machines to other languages.

Answer 3

You can use fsm2regex , an online tool that does this work.

Answer 4

I find the best tool I've used is greenery . This is the FSM / regex conversion library for python. You can learn more about the library here and the algorithm used is well described.

---

Example

The model that can be found on the website can be transformed as follows:

 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) 

The conclusion is as follows:

 >>> print(machine) name final? ab ------------------ * 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) 

---

Note

The PYPI version has some assertion issue and the github version has some memory issues, but the python combination of version 3.x + github is amazing.

Answer 5

I have implemented a state exclusion algorithm for the http://www.brics.dk/automaton/ Java package. The implementation is based on the algorithm shown in Sipser, Michael. Introduction to computational theory. Volume 2. Boston: Thomson's Technology Course, 2006.

You can check this out at https://github.com/julianthome/autorex . We will be glad to receive feedback.

Best wishes and best wishes, Julian