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
alphabet.
a. Let language L = {b, zebra, eee}. What are the elements of L^{3} ? How many words are in L^{3} ?
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.)
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 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 ?
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.