Re: Minimal DFA properties

daw@mozart.cs.berkeley.edu (David Wagner)
24 Mar 2002 15:30:47 -0500

          From comp.compilers
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)
| List of all articles for this month |
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.