```Homework #2

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

Solution:
Base case.
|X| = 1.  The power set of X, where X = {a1}, is
{{}, {a1}}, consisting of 2 elements.
Since 2^|X| = 2, the property holds.
Other base cases.
|X| = 2.  The power set of X, where X = {a1, a2}, is
{{}, {a1}, {a2}, {a1,a2}}, consisting of 4 elements.
Since 2^{X} = 4, the property holds.

|X| = 3.  The power set of X, where X = {a1, a2, a3}, is
{{}, {a1}, {a2}, {a3}, {a1,a2}, {a1,a3}, {a2,a3},
{a1,a2,a3}}, consisting of 8 elements.
Since 2^|X| = 8, the property holds.

Inductive hypothesis.
Assume that the property holds when |X| = n, X = {a1, a2, ..., an}.
That is, |P(X)| = 2^n.

Inductive step.
Prove that the property then holds when |X| = n+1.
We know that the power set of X, where X = {a1, a2, ..., an+1},
consists of all the subsets of X.  We can generating all the subsets
by listing the subsets of {a1, ..., an} and then repeating these
subsets with the addition of an+1.

We know from the inductive hypothesis that the number of
subsets of {a1, ..., an} is 2^n.  We also know that the number of
subsets of {a1, ..., an, an+1} is double that of {a1, ..., an}, so
|P({a1,...,an})| = 2*|P({a1,...,an})| = 2*2^n = 2^{n+1}.
Thus the property holds.

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.

Solution:  Let the number of people in the group be n.  The least number
of acquantances is 0 and the greatest is n-1.  Also note that when person
x is acquainted with person y, person y is also acquainted with person x.

Let us show this proof by contradiction.  If every person has a different
number of acquaintances, and we order them then the set of numbers of
acquaintances must be {0, 1, ..., n-1}.  However, if one person has
n-1 acquaintances than he/she is acquainted with every one else in the
group, thus no person can have 0 acquaintances.  Now, instead of the
possible numbers of acquaintances ranging from 0 to n-1, they range from
1 to n-1.  Because there are only n-1 possibilities and n people, the
pigeonhole principle proves that at least two people have the same number
of acquaintances in the group.

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.

Solution:
a) Except for a possible pair of as and/or bs, the strings alternate betwee       a and b.  A regular expression for alternating as and bs is
(b v e)(ab)*(a v e) (as well as the dual expression (a v e)(ba)*(b v e))       In order to allow a pair of as, we can split the term (ab)* in two parts
and insert (a v e) to obtain (b v e)(ab)*(a v e)(ab)*(a v e).
We will do the same thing to allow a pair of bs and union the two
expressions to generate the answer.

((b v e)(ab)*(a v e)(ab)*(a v e)) v ((a v e)(ba)*(b v e)(ba)*(b v e))

b) (b v e)(a v ab)*(b v ab)*(a v e)

c) (a*b*(a v e)) v (a*b*aa)*

d) (a v b v e)*bab(a v b v e)*

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)]*

Solution:
a) The set of all strings over {0,1}* such that no odd number of adjacent
"0"s (0 surrounded by "1"s) can be found after seeing an odd number of
adjacent "1"s.

b) The set of all strings over {0,1}* that have an even-numbered length
of 2 or greater and do not end in 0100, 1000, 0111, or 1011.

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

Solution:

Base Case:  Let i = 0.  (w^R)^0 = (w^0)^R = e, so the property holds.
Let i = 1.  (w^R)^1 = w^R and (w^1)^R = w^R,
so the property holds.
Inductive Hypothesis.  Assume the property holds for i<=n.
Inductive Step:  Prove that the property then holds for i = n+1.
Note that w^{n+1} = w^n . w, and (w^n+1)^R = (w^n . w)^R = w^R . (w^n)^R       Also note that (w^R)^{n+1} = w^R . (w^R)^n.
From the inductive hypothesis (w^R)^n = (w^n)^R, so the property holds.
```