6 Apr 2002 23:13:26 -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: | "Dennis Mickunas" <mickunas@cs.uiuc.edu> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.