20 Apr 2003 17:13:04 -0400

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) |

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.