# 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.

-