|Minimal DFA properties email@example.com (Paul J. Lucas) (2002-03-24)|
|Re: Minimal DFA properties firstname.lastname@example.org (2002-03-24)|
|Re: Minimal DFA properties email@example.com (2002-03-31)|
|From:||firstname.lastname@example.org (David Wagner)|
|Date:||24 Mar 2002 15:30:47 -0500|
|Organization:||University of California, Berkeley|
|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.
Return to the
Search the comp.compilers archives again.