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.