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