Re: automata to regexp

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

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