hey buddy i cannot solve yr problem but may be u can solve mine
i need a cog\de that can conver a regular expresion to NFA and then to DFA
andthen compare the 2 regular expressions to find out if they are equal.
please do reply in either case if u wish to help me or not .
thank u email@example.com
Like if I enter ab* it will draw a state diagram ;) I know they have ones that convert nfa to dfa but I have yet to find one that will draw from an expression. Thanks
For obvious reasons I can't recite code from memory that'll do what you're asking for, but there does exist a regexp-->DFA algorithm...on paper. You're probably already familiar with it, it's the one where you create a start edge labelled with the original expression, and then perform a sequence of splits/branches/loops based on the operators in the expression.
That can be done in code just as easily (if not easier) - but you'll have to represent the DFA as a table. Specifically, a list of edges. Take the starting edge (labelled with the original expression) and apply a transformation according to the highest-precedence operator in the expression. Then recurse onto the resulting edge(s) and do the same for their labels.
I recommend doing it in Scheme ; )
The main function might look like
(elaborate-DFA edge next-newstate),
where edge is a representation of a transition in the graph of the form
(origin destination label).
Of course, if you just want a nifty little app that'll draw pretty pictures for you, I believe there's one called Deus Ex Machina. Google may have something to say about that.