Hints for HW 3
--------------

1) (c) This means that a b can never directly follow another b.

(d) and (e):  describe the sets in mathematical English.   The
descriptions should be simple.   

-------------------------------------------
2) You need to use the product construction, where the states
of the new machine are pairs of states, one from the first machine
and one from the second.    This construction works the same for
union and intersection, except for which states you mark as final.

(a) is not hard.   It's just to make you review the construction details.

(b) Before you try to write formal notation, explain to yourself in
English what is supposed to happen if the combined machine M
encounters a character that's in one alphabet but not in the other.
How does this situation look from the point of view of M1?  M2?

-------------------------------------------
3) If you downloaded this problem set right after it was posted
late Tuesday, there was a typo in the first line of part (a).
Look at the new version and correct two bits of the tuple notation by
hand on your printout.

Draw some sketches to see what's going on.   Either sketch using
specific small input DFAs or else draw a partial diagram with boxes
(like we used in class Thursday the 31st).   Don't try to write
formal notation until you have a good mental picture of the construction.

(b) A complete answer requires tuple notation.  A sketch or informal
description isn't a sufficient but itself, but it often helps the
grader understand your tuple notation.   This typically improves your
score, especially if your tuple notation was unusual or buggy.

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

4) The formal construction isn't much different from 2b.  The
difference is that you need to give full tuple notation (not just
delta and F).  And you need to read our wordy specification and figure
out what it means.

Again, first figure out in English and/or pictures what is supposed to
be happening.   Only write formal notation when you have a good mental
picture of what the notation is supposed to be accomplishing.

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

5) This is like the "balanced string" problem from HW 2.   You
might want to look at its model solutions before attacking this one.

(b) Pick helpful names for your states.   First do the case where
k is even.   Then extend to the case where k is odd (e.g. aabaa is
also a palindrome).

(c) Look at your state names.   What is each state remembering?   Can
any finite set of states work for this problem?

(d) This can be answered in one short sentence.   What have we
actually proved about unions?

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