Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
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
Crossposted on SO. –  Raphael Oct 10 '12 at 19:50
add comment

marked as duplicate by Raphael Oct 10 '12 at 6:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

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.

share|improve this answer
add comment