|Regular Expression Minimization email@example.com (Jose Joao Morais) (2003-04-13)|
|Re: Regular Expression Minimization gdb@dbSystems.com (David Butler) (2003-04-20)|
|Re: Regular Expression Minimization firstname.lastname@example.org (2003-04-20)|
|From:||"David Butler" <gdb@dbSystems.com>|
|Date:||20 Apr 2003 17:13:04 -0400|
|Organization:||Prodigy Internet http://www.prodigy.com|
|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" <email@example.com> 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
Return to the
Search the comp.compilers archives again.