DFA complement/intersection problem

If I have two languages:


L = a*
M = (a|b)*


it's obvious that L <= M (L is a subset of M) because all
sequences of A* are also sequences of (a|b)*. However, when I
write code for this, I get L <= M and M <= L which is wrong.
From:


L <= M === intersect(L,~M) = 0


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.


Then, to compute the intersection, you do a cross product of
all the states in L and M and relabel each pair of states (p,q)
in the intersected langauge N. (You also do stuff with the
transitions, but that's not relevant here.) Furthermore, a
state in N is accepting iff (p,q) is accepting.


Now, since ~M has no accepting states, N can't either; therefore
N is empty and this shows that L <= M.


However, if you do this for M <= L, you get the same result
because ~L has no accepting states so N' = intersect(M,~L)
doesn't either; therefore N' is empty and M <= L. But this
isn't right!


What am I missing? Where is the mistake.


- Paul

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