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

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