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.