Prove that {0,1}* is countably infinite.

Prove that the set of all subsets of {0,1}* is not countably infinite.

Can we assign a unique name to each subset of {0,1}* ? Explain your answer.

List the three shortest strings in {0

^{n}10^{n+2}1| n ≥1}.Describe the set of strings denoted by {0

^{n}10^{n+2}1| n ≥1}*. How many strings are there of length less than or equal to 16?

Exercise 2.2.4 in the text.