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 L^{3}? How many words are in L^{3}? ANS: L^{3}contains 27 words. Elements of L^{3}are concatenations of 3 elements from L in any order. b. What is P(L^{3}) ? How many elements are in P(L^{3}) ? (Note: P here denotes the power set operator. See page 10 of the text.) ANS: P(L^{3}) contains 2^{27}elements. Elements of P(L^{3}) are all subsets of L^{3}. 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 N_{2}. Compute N_{2}on all strings of 1's and 2's of length less than 5. Is N_{2}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}.