Hints for Problem Set 2
-----------------------

(1) Is not intended to be difficult.   

---------------------------------------------------------------------

(2) Be sure that your automata have start and final states marked.
Also be sure that each state has exactly one outgoing transition on
each character in Sigma.
  (a) Double-check that your machine does the right thing on
      the empty string.   Numbers with leading zeros are allowed.
  (b) The language definition doesn't actually force the string
      to contain any 1's or 0's.   Also it doesn't say anything about
      the number of 1's allowed at the start and end of a string.
      So, for example, 01110110 isn't in the language, but
      1110110 is.

---------------------------------------------------------------------

(3) This isn't intended to be tricky, merely to force you to walk
through the details of the product construction.  Notice that each
state in your diagram should be labelled with a PAIR of letters,
e.g. you might have a state labelled (A,D).

---------------------------------------------------------------------

(4) Your answers need to describe the situation in general terms, for
any DFAs M and N.  However, you may find it helpful to first
experiment with some particular DFAs, for which you can draw state
diagrams.


(a) You should assume that the three new states weren't in the
original set Q.  (This is sometimes said explicitly and sometimes
not.)

(b) You should assume that Q and R have no elements in common.
(If they did, you could rename states to make them different.)

Your answers need to be in formal mathematical notation.   However,
it is sometimes helpful to add a picture of key parts of the state
diagram and/or some English describing the idea behind your notation.
If your notation isn't exactly correct, this often allows us to give
you more partial credit.

The character # may look special, but it's just an input character
just like the ones in Sigma.

---------------------------------------------------------------------

(5) 

(b) Beware:  getting the solution approximately right isn't too 
difficult, but it may be hard to nail down the details exactly.

(c) You are trying to prove a set equality X = Y.  The normal
method for doing this is to prove that X is a subset of Y, and
then that Y is a subset of X.