Re: Regular Expression Minimization

"David Butler" <gdb@dbSystems.com>
20 Apr 2003 17:13:04 -0400

          From comp.compilers
Related articles
Regular Expression Minimization jjoao@netcabo.pt (Jose Joao Morais) (2003-04-13)
Re: Regular Expression Minimization gdb@dbSystems.com (David Butler) (2003-04-20)
Re: Regular Expression Minimization benjaminabernathy@hotmail.com (2003-04-20)
| List of all articles for this month |
From: "David Butler" <gdb@dbSystems.com>
Newsgroups: comp.compilers
Date: 20 Apr 2003 17:13:04 -0400
Organization: Prodigy Internet http://www.prodigy.com
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.


www.dbSystems.com/stc/


David
gdb@dbSystems.com




"Jose Joao Morais" <jjoao@netcabo.pt> 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.