Regular Expression Minimization

Jose Joao Morais <>
13 Apr 2003 12:43:05 -0400

          From comp.compilers

Related articles
Regular Expression Minimization (Jose Joao Morais) (2003-04-13)
Re: Regular Expression Minimization (David Butler) (2003-04-20)
Re: Regular Expression Minimization (2003-04-20)
| List of all articles for this month |

From: Jose Joao Morais <>
Newsgroups: comp.compilers
Date: 13 Apr 2003 12:43:05 -0400
Organization: Compilers Central
Keywords: lex, question
Posted-Date: 13 Apr 2003 12:43:05 EDT


        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

        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

Post a followup to this message

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