6 Apr 2002 23:41:07 -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: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 6 Apr 2002 23:41:07 -0500 |

Organization: | Compilers Central |

References: | 02-03-189 |

Keywords: | DFA, lex |

Posted-Date: | 06 Apr 2002 23:41:07 EST |

*> I first have two minimal DFA for both languages:*

*>*

*> L: (s0) --{a}-> (s0)*

*> M: (t0) --{a|b}-> (t0)*

*>*

*> What am I missing? Where is the mistake?*

Simple your DFA's, while minimal, are not complete. They do not have

transitions for every element of \Sigma (the input alphabet). If you

put the transitions in L for what it does on seeing a "b", you will

see that L has 2 states (the non-accepting state that is entered once

the first b is seen and the accepting state which is for only a's have

been seen). BTW, If there is also a symbol "c" in your alphabet, M

will also have two states, if not it will have only one.

Thus,

L: (s0) --{a}-> (s0)

(s0) --{b}-> s1 // non-accepting

s1 --{a,b}-> s1

In any case, adding those extra state(s) and transitions will resolve

your problem.

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. Web Site : http://world.std.com/~compres

3 Proctor Street voice : (508) 435-5016

Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.