Homework #2

1.  Prove by induction that |P(X)| = 2^|X| for all finite sets of size one
    or greater.

2.  Show that in any group of people there are at least two persons that have
    the same number of acquaintances within the group.  Use the pigeonhole
    principle to complete this proof, and assume that an acquaintance must be
    with a person other than themselves.

3.  Write regular expressions for each of the following languages over the
    alphabet {a, b}.  Provide justification that your regular expression
    is correct.

    a) The set of all strings with at most one pair of consecutive "a"s or at
       most one pair of consecutive "b"s, but not both.
    b) The set of all strings in which every pair of adjacent "a"s appears
       before any pair of adjacent "b"s.
    c) The set of all strings not containing bab as a substring.
    d) The set of all strings containing bab as a substring.

4.  Describe in English the sets denoted by the following regular expressions.
    a) (11 v 0)*(00 v 1)*
    b) [00 v 11 v (01 v 10)(00 v 11)*(01 v 10)]*

5.  Prove, using induction on i, that (w^R)^i = (w^i)^R for all strings
    w in Sigma*.