Re: Regular Expression Minimization

"David Butler" <>
20 Apr 2003 17:13:04 -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: "David Butler" <>
Newsgroups: comp.compilers
Date: 20 Apr 2003 17:13:04 -0400
Organization: Prodigy Internet
References: 03-04-042
Keywords: lex
Posted-Date: 20 Apr 2003 17:13:03 EDT

I have used a tool to "minimize" nasty regular expressions,
but it takes a little work. The input into the tool is a table
because that was the problem domain it was written for.

The state elimination algorithm used is basically a karnaugh map.
But that is only the first step to minimization.

You may find it useful, nonetheless.


"Jose Joao Morais" <> wrote in message
> 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)?

Post a followup to this message

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