6 Apr 2002 22:54:06 -0500

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

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.