DFA complement/intersection problem

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

Return to the comp.compilers page.
Search the comp.compilers archives again.