```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*.
```