Re: DFA complement/intersection problem

rcbilson@plg2.math.uwaterloo.ca (Richard C Bilson)
6 Apr 2002 22:54:06 -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: rcbilson@plg2.math.uwaterloo.ca (Richard C Bilson)
Newsgroups: comp.compilers
Date: 6 Apr 2002 22:54:06 -0500
Organization: University of Waterloo
References: 02-03-189
Keywords: lex, DFA, theory
Posted-Date: 06 Apr 2002 22:54:06 EST

Paul J. Lucas <pjl@mac.com> wrote:
>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.


What happens to machine L when it reads a 'b'? You haven't defined
the transition function in this case. I assume that this is because
you have an implicit "error" state. I think that making this "error"
state explicit will solve most of your problems.


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


This makes sense, since M accepts any strings from the alphabet {a,b}.
Therefore, the complementary machine will accept nothing.


Applying the analogous construction for L as you state doesn't work the
same way, though -- L doesn't accept every string in {a,b}, just those
without 'b'. It makes sense that the complementary machine would accept
strings with a 'b' somewhere.


Richard


Post a followup to this message

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