Re: Minimal DFA properties

thp@cs.ucr.edu
31 Mar 2002 23:31:20 -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: thp@cs.ucr.edu
Newsgroups: comp.compilers
Date: 31 Mar 2002 23:31:20 -0500
Organization: University of California, Riverside
References: 02-03-163
Keywords: DFA
Posted-Date: 31 Mar 2002 23:31:20 EST

Paul J. Lucas <pjl.removethis@removethistoo.mac.com> 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.


Tom Payne

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.