9 Jun 1998 11:56:17 -0400

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

From: | Janaki S <janaki@csa.iisc.ernet.in> |

Newsgroups: | comp.compilers |

Date: | 9 Jun 1998 11:56:17 -0400 |

Organization: | Compilers Central |

References: | 98-05-136 |

Keywords: | DFA |

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

=> =>

There was a mistake in the previous message i sent you.

The problem can be solved with the Hopcroft-Ullman, et.al

algorithm itself in a time of O(n^3) using a proper dynamic programming

startegy.

It has to come something like:

k ->

0 1 2 3 4 5 6 7 ......

-------------------------------------

(i-1)*n + j | * * * * * * * * * * * |

-------------------------------------

| | * * * * * * * * * * * |

V -------------------------------------

| * * * * * * * * * * * |

-------------------------------------

| * * * * * * * * * * * |

-------------------------------------

| * * * * * * * * * * * |

-------------------------------------

| * * * * * * * * * * * |

-------------------------------------

| * * * * * * * * * * * |

-------------------------------------

| * * * * * * * * * * * |

-------------------------------------

| * * * * * * * * * * * |

-------------------------------------

Now filling the first column can be done in O(n^2) time, then

extending it towards the right (each column taking O(n^2) time), we can

fill the whole table in O(n^3) time, and hence the result can be obtained

in O(n^3) time.

As such, i have no idea about any other algorithm for doing this.

I would like to know about it, if there is one.

- Janaki

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.