Re: automata to regexp

Janaki S <>
3 Jun 1998 01:57:53 -0400

          From comp.compilers

Related articles
automata to regexp (Ranjit Jhala) (1998-05-30)
Re: automata to regexp (Janaki S) (1998-06-03)
Re: automata to regexp (Janaki S) (1998-06-09)
| List of all articles for this month |

From: Janaki S <>
Newsgroups: comp.compilers
Date: 3 Jun 1998 01:57:53 -0400
Organization: Compilers Central
References: 98-05-136
Keywords: DFA

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).

- Janaki
Janaki S
Research Student (MSc Engg)
Computer Science and Automation
Indian Institute of Science
Bangalore - 560 012

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.