# Re: DFA complement/intersection problem

## "Dennis Mickunas" <mickunas@cs.uiuc.edu>6 Apr 2002 23:13:26 -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: "Dennis Mickunas" Newsgroups: comp.compilers Date: 6 Apr 2002 23:13:26 -0500 Organization: University of Illinois at Urbana-Champaign References: 02-03-189 Keywords: DFA, lex Posted-Date: 06 Apr 2002 23:13:26 EST

"Paul J. Lucas" <pjl@mac.com> wrote in message

> 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)
....

> 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.

The "flipping accepting/nonaccepting states" method works only if L is
specified as a *complete* DFA (over the alphabet {a,b}), namely

L:(s0)--(a)->(s0)
(s0)--(b)->(s1)
(s1)--(a|b)->(s1)

where (s1) is non-final. Now it's obvious that ~L=a*b(a|b)* (i.e.
strings that contain at least one b).

Post a followup to this message