13 Apr 2003 12:43:05 -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: | Jose Joao Morais <jjoao@netcabo.pt> |

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 |

Hello,

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

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.