|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)|
|Date:||31 Mar 2002 23:31:20 -0500|
|Organization:||University of California, Riverside|
|Posted-Date:||31 Mar 2002 23:31:20 EST|
Paul J. Lucas <firstname.lastname@example.org> 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?
Let L1 be all strings of odd length and L2 be all strings of even
length. The minimal machine for each of these languages must have at
least two states. The minimal machine for their union, however,
requires only one state.
Return to the
Search the comp.compilers archives again.