Is there a program that creates DFA from expression

[Neco_Coneco]

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

[bunty]

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
[e-mail]

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

[Neco_Coneco]

Sorry I don't know. :sad:

[Nuez_Jr]

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.