0

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

3
Contributors
3
Replies
4
Views
13 Years
Discussion Span
Last Post by Nuez_Jr
0

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
nilay007@rediffmail.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

0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.