Re: automata to regexp

Janaki S <janaki@csa.iisc.ernet.in>
3 Jun 1998 01:57:53 -0400

          From comp.compilers
Related articles
automata to regexp Ranjit.Jhala@irisa.fr (Ranjit Jhala) (1998-05-30)
Re: automata to regexp janaki@csa.iisc.ernet.in (Janaki S) (1998-06-03)
Re: automata to regexp janaki@csa.iisc.ernet.in (Janaki S) (1998-06-09)
| List of all articles for this month |
From: Janaki S <janaki@csa.iisc.ernet.in>
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.


Hi,
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
India
--

Post a followup to this message

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