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