# Re: DFA complement/intersection problem

## Kenn Heinrich <heinrich@idirect.com>6 Apr 2002 23:13:48 -0500

From comp.compilers

Related articles
DFA complement/intersection problem pjl@mac.com (Paul J. Lucas) (2002-03-31)
Re: DFA complement/intersection problem rcbilson@plg2.math.uwaterloo.ca (2002-04-06)
Re: DFA complement/intersection problem mickunas@cs.uiuc.edu (Dennis Mickunas) (2002-04-06)
Re: DFA complement/intersection problem heinrich@idirect.com (Kenn Heinrich) (2002-04-06)
DFA complement/intersection problem cfc@world.std.com (Chris F Clark) (2002-04-06)
| List of all articles for this month |

 From: Kenn Heinrich Newsgroups: comp.compilers Date: 6 Apr 2002 23:13:48 -0500 Organization: Posted via Supernews, http://www.supernews.com References: 02-03-189 Keywords: DFA Posted-Date: 06 Apr 2002 23:13:48 EST

"Paul J. Lucas" wrote:

<snipped some bits out...>

> I first have two minimal DFA for both languages:
>
> L: (s0) --{a}-> (s0)
> M: (t0) --{a|b}-> (t0)
>
> That is: each DFA has a single state that is accepting. For L,
> there is a single transition on 'a' back to s0; for M, there
> are two transitions: one each for 'a' and 'b' back to t0.
>
> If I understand Hopcroft, et al, correctly, to compute ~M, the
> complement of M, you simply flip all the accepting and non-
> accepting states. For M, since there is only one state, it
> becomes non-accepting.

Your construction of the ~L machine is not correct. The language ~L
is not empty but the language accepted by your automaton is empty,
since there are no accepting states.

I think you need to complement the acceptance of each state *after*
you augment your DFA to make the state transition function a total
function; i.e. you need to add a non-accepting "dump state" and
transitions from each state s0,s1,...,sn to the dump state for every
input character which does not have an associated transition in the
original machine. Then the construction you describe will yield a
machine which accepts ~L, and proceed from there.

- Kenn

Post a followup to this message