Hints for HW 3
==============

Problem 1
   If you aren't sure what an NFA does, look for some short
   test strings that it does/doesn't accept.   Then try to
   extract the general pattern.


Problem 2
   Start with the start state {q0} and follow transitions, to
   trace out all the states reacheable from the start state.
   For each state you generate, be sure to explore transitions
   on both a and b.

   Make sure your state names are legible.  q2 and q3 can look very
   similar if your handwriting gets sloppy.

Problem 3
   A string in L consists of five parts.   Your NFA should have
   a subsection that handles each part.  However, there are no special
   characters to mark the boundaries between the parts.  So the NFA
   will have to "guess" when to transition between the subsections,
   e.g. it will have several transitions on the same character or an 
   epsilon transition.

   Do not try to build a DFA.   Show us that you understand how to use
   the features provided by NFAs.


Problem 4
   Did you check the solution sheet for PS 1, to make sure you
   understand how inductive definitions work?

   (a) If your description of L is complicated, it's probably wrong.
   Make sure you've tried all the ways of generating new elements of L.
   In rule (d), remember that w and x might happen to be the same string.

   (b)    A good method for doing the first part is "structural induction".
   The outline for a structural induction proof would look like
     base case:  epsilon satisfies D
     inductive step:  suppose that w and x are strings satisfying D.
         [do some work]
         conclude that aw, bwb, and wx all satisfy D.
     By induction, all strings in L satisfy D.

   (c) You need to give a procedure that takes some random string x
   satifying D and describes how to construct x using the rules
   (a)-(d).  It may be helpful to first write a procedure for handling
   some subset of these strings, e.g. the strings containing only a's.


   Notice that your answer to part (c) should not be the same as your
   answer to part (b). 


Problem 5
   The modifications are not complex and your definitions will look mostly
   similar to the originals in the book.  The point of this problem is
   to make you read the definitions carefully, so you understand the
   details.