|automata to regexp Ranjit.Jhala@irisa.fr (Ranjit Jhala) (1998-05-30)|
|Re: automata to regexp email@example.com (Janaki S) (1998-06-03)|
|Re: automata to regexp firstname.lastname@example.org (Janaki S) (1998-06-09)|
|From:||Janaki S <email@example.com>|
|Date:||3 Jun 1998 01:57:53 -0400|
On Sat, 30 May 1998, Ranjit Jhala wrote:
=> Can someone please tell me what the fastest algorithms to
=> convert a DFA / NFA to a regular expression are . I know about the
=> algorithms in Hopcroft-Ullman etc. I was wondering if there is
=> anything faster.
I think the algorithm in Hopcroft and Ullman is the best, and it
can be run in O(n^2) time, if you use a proper dynamic algorithm which
comes to the same effect as the equation given in the book.
I don't know about anything better, and i would also like to know
whether there is any other algorithm, which can do better than O(n^2).
Research Student (MSc Engg)
Computer Science and Automation
Indian Institute of Science
Bangalore - 560 012
Return to the
Search the comp.compilers archives again.