24 Mar 2002 15:30:47 -0500

Related articles |
---|

Minimal DFA properties pjl.removethis@removethistoo.mac.com (Paul J. Lucas) (2002-03-24) |

Re: Minimal DFA properties daw@mozart.cs.berkeley.edu (2002-03-24) |

Re: Minimal DFA properties thp@cs.ucr.edu (2002-03-31) |

From: | daw@mozart.cs.berkeley.edu (David Wagner) |

Newsgroups: | comp.compilers |

Date: | 24 Mar 2002 15:30:47 -0500 |

Organization: | University of California, Berkeley |

References: | 02-03-163 |

Keywords: | lex, theory, DFA |

Posted-Date: | 24 Mar 2002 15:30:47 EST |

Paul J. Lucas wrote:

*>If one has two minimal DFAs representing regular languages and one*

*>takes their union and intersection (separately), are the resulting*

*>DFAs also minimal or do you you have to rerun a minimization algorithm*

*>on the results to get minimal DFAs?*

Not necessarily minimal, I believe (assuming you use the product

construction for union and intersection). For instance, suppose you take

the union of a n-state minimal DFA with itself. The product construction

will give something with n^2 states, but the minimal DFA has n states

(it's just what you started with), hence the product construction's

output is not minimal in this case.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.