Homework 1

CS 3810 – Summer 2008

1.  

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

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

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

2.  

   1. List the three shortest strings in {0ⁿ10ⁿ⁺²1| n ≥1}.

   2. Describe the set of strings denoted by {0ⁿ10ⁿ⁺²1| n ≥1}*. How many strings are there of length less than or equal to 16?

3. Exercise 2.2.4 in the text.