6 Apr 2002 23:13:48 -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: | Kenn Heinrich <heinrich@idirect.com> |

Newsgroups: | comp.compilers |

Date: | 6 Apr 2002 23:13:48 -0500 |

Organization: | Posted via Supernews, http://www.supernews.com |

References: | 02-03-189 |

Keywords: | DFA |

Posted-Date: | 06 Apr 2002 23:13:48 EST |

"Paul J. Lucas" wrote:

<snipped some bits out...>

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

Your construction of the ~L machine is not correct. The language ~L

is not empty but the language accepted by your automaton is empty,

since there are no accepting states.

I think you need to complement the acceptance of each state *after*

you augment your DFA to make the state transition function a total

function; i.e. you need to add a non-accepting "dump state" and

transitions from each state s0,s1,...,sn to the dump state for every

input character which does not have an associated transition in the

original machine. Then the construction you describe will yield a

machine which accepts ~L, and proceed from there.

- Kenn

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.