CS 535
                                                       Fall 2010

                      Assignment #0 (not graded)
                          
                    Brief answers to some of the problems

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

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

ANS: L3 contains 27 words. Elements of L3 are concatenations of  3 elements from L in any order.

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

ANS: P(L3) contains 227 elements. Elements of P(L3) are all subsets of L3.

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

ANS:  L* is the set of all finite string of words from L. L* and L** are 
both infinite and the two sets are equal (have exactly the same elements). 

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 ?

ANS: Yes, just do the computation to see this. 

Is it one-to-one on all strings of 1's and 2's ? Why or why not ? 

ANS: Yes, as long as by strings of 1's and 2's we mean finite strings. 

3. Homework 1.2 on page 7

ANS: This one was graded. See comments on your paper.

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.

ANS: This one was graded. See comments on your paper.

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

ANS: This one was graded. See comments on your paper.

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

ANS: This is easy - maybe the {reals between 0 and 1} and {reals between  1 and 2}  

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

ANS: 
We enumerate the desired set in stages i, with even, that is i=2,4,6,...
At stage i we enumerate exactly i strings, namely each of 
100..0, 0100...0, 00100...0, .... 00...01 where the length of each string
is i.

More formally at stage i we enumerate all binary strings composed of 
t 0's following by a 1 followed by i-t-1 0's, where t=0,1,2,...i-1.

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.

AND: B={0,1}* and A={all strings of 0's}. So B &minus A is infinite
as it is the set of all binary strings which have at least one 1 in them. 

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

ANS: This is not hard but can be confusing and takes some organization. 

For example:

We enumerate the desired set in stages i, with i=3,4,5,...
At stage i we enumerate all sets of three natural numbers from the set
{1,2,3,...,i} which have not been enumerated at previous stages. 

So at stage 1, {1,2,3} is enumerated.
And at stage i, i>1, we list {1,2,i}, {1,3,i}, {1,4,i},...{1,i-1,,i},
{2,3,i}, {2,4,i}, ...,{2,i-1,i}, .... {3,4,i},...{3,i-1,i},...., {i-2,i-1,i}.

Note: For any set of 3 natural numbers {j,k,l}, this set will be
enumerated during stage t where t= max{j,k,l}.