Regular Expression Minimization

Hello,


        I know the problem of finding the optimal minimal regular
expression equivalent to a given regular language is NP-complete, but
I have another problem:


Given a DFA and using the "state elimination" algorithm to convert the
given DFA to an equivalent regular expression, which order (on the
states of the DFA) in which to remove the states so that the resulting
expression is minimal (among the ones obtained by different removal
orderings)?




        I have tried the following: compute the lengths of the regular
expressions associated with the edges of the GTG - General Transition
Graph - associated with the DFA and let that be the weight of the GTG,
then compute the weight that removing a vertex from the graph will
increase in the weight of the GTG and in each step remove the vertex
that less augments the weight of the GTG.


        This algorithm is better in many cases than simply removing vertices
in any "blind" order, but also in many cases does not give the minimal
regular expression (among the ones obtained by different removal orderings).


        Does anyone has any ideas about how to improve this algorithm, or a
different but better one?


        Is the problem I described also NP-complete?


        Thank you

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