Re: DFA complement/intersection problem

"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

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