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 <heinrich@idirect.com>
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

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