CS 535
                                                       Fall 2010

                      Assignment #0 (not graded)

Date Due: Thursday, September 9

Reading: Chapter 1,  pages 1-21, Chapter 2, pages 22-36,  and Chapter 3, pages 41-47

Problems :

1. Assume we take the 26 English letters as our alphabet, and consider words and languages over this

a. Let language  L = {b, zebra, eee}.   What are the elements of L3 ?  How many words are in  L3 ?

b. What is P(L3) ? How many elements are in  P(L3) ?
(Note: P here denotes the power set operator. See page 10 of the text.)

c. What is L* ? How many words are in  L* ? What is L** ?

2. The k-adic representation is defined in section 1.2 of the text.
Consider the 2-adic representation of the integers and the function N2. 
Compute  N2 on all strings of 1's and 2's of length less than 5. 
Is  N2 one-to-one on these strings ?
Is it one-to-one on all strings of 1's and 2's ? Why or why not ? 

3. Homework 1.2 on page 7

4. Homework 1.6 on page 9

You should start by stating clearly what is is you need to prove, given the definitions of card(S)
and of one set having cardinality &le another set.

5. Put the formula F = ((not a) &and b &and (not c)) &or ( b &or (not d))  in conjunctive normal form.  

6. Give an example of two different infinite and disjoint uncountable sets of real numbers. 

7. Show that the set of strings in {0,1}* which have even length and 
exactly one 0 in them is countable. 

8. Give an example of two different countable and infinite languages A and B
over {0,1} with A a subset of B and  whose difference B &minus A is infinite.

9. List (that is enumerate, see page 8) all the sets of natural numbers 
which contain exactly three natural numbers.