# Program that generates a regular expression from an FA [duplicate]

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.

• 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). – Raphael Oct 10 '12 at 6:39
• 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 – user3115 Oct 10 '12 at 7:59
• 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). – Raphael Oct 10 '12 at 13:13
• – Raphael Oct 10 '12 at 19:50