DFA complement/intersection problem

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


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