Hints for Homework 1
--------------------

Chapter 0 of Sipser is a good place look up forgotten definitions.
Some reviews on the web are at:
   http://www.maths.mq.edu.au/~wchen/lndmfolder/lndm.html
   http://en.wikipedia.org/wiki/Set

A common error in such calculations is to forget about, or do the
wrong thing with, the empty string or the empty set.  Double-check
these cases.

1) See Sipser p. 6.  

2) See Sipser pp. 13--14 for definitions of string operations.

3) What happens if n is zero?

4) Start by putting (3,5) into your set S.  Then start adding whatever
extra elements are required to satisfy (b)-(d).  Remember that these
rules can feed into one another.  That is, if one of these rules
(e.g. c) causes an item X to be added to S, then another rule (e.g. b)
could use X to derive another element that must also be added.

When you've found enough concrete values that must be in S, try to
figure out what the pattern is.

  "Explain why it is correct" means that we want a convincing 
informal explanation, but a formal proof is not required.

(5) You may wish to consult a discrete structures text, to help you recall
useful standard identities.