Possible Duplicate:
How to convert finite automata to regular expressions?

Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation.

To make things less complicated I want to limit the number of states to about 4, assume the FA is in minimal form and that the FA has only one FinalState and only one StartState.

Ive been thinking about it for a while now and I think the first obvious thing to do would be to create a transition table for the FA.

So an FA could look like this:

NumberOfStates 4 
StartState   1 
FinalState   4 
StateNumber  NextStateA   NextStateB
1            2            4
2            3            2
3            4            4

And would generate the regular expression: b + (ab*a(a + b))

Ive been racking my brain for hours but am stumped on how to go about this. Any ideas is greatly appreciated.

  • $\begingroup$ That has been covered extensively here. Please look at the questions the system proposes as similar before posting. It's not always perfect, but in this case, the older question showed up (I know because it showed up immediately in the closing dialog). $\endgroup$
    – Raphael
    Oct 10, 2012 at 6:39
  • $\begingroup$ Can you refer me to any code thats already been implemented? I looked at your questions answers but I have a hard time figuring out the heavily based math $\endgroup$
    – user3115
    Oct 10, 2012 at 7:59
  • $\begingroup$ This site is all about computer science, not about programming. If you are after implementations, you should go to Stack Overflow (and link the formal stuff there). $\endgroup$
    – Raphael
    Oct 10, 2012 at 13:13
  • $\begingroup$ Crossposted on SO. $\endgroup$
    – Raphael
    Oct 10, 2012 at 19:50

1 Answer 1


Here's one resource on the matter: www.cs.dartmouth.edu/~ac/Teach/CS39.../lec09dfa2regexp.pdf

There's a commonly known Dynamic Programming algorithm which can do it. The link I send outlines the algorithm, though it doesn't convert to code. The DP algorithm is pretty common (I think it's usually used in the proof that DFA and RE are equivalent) so if you're looking for the code, it's probably out there somewhere.