## CS 301, Spring 2012, Problem Set 2

1. Give examples to show that:
1. The intersection of two coubtably infinite sets can be finite
2. or it can be countably infinite.
3. The intersection of two uncountable sets can be finite,
4. or it can be countably infinite,
5. or it can be uncountable.
2. Prove that Galilelo was correct when he wrote in 1632 that "There are as many squares as there are numbers, because they are just as numerous as their roots," by showing that there is a 1-1 onto function from {\cal N} = \{0, 1, 2, \ldots \} to the set of all squares of nonnegative integers.
3. In class and in the Sipser book, we defined |A| = |B| if and only if there is a 1-1 onto function f: A \rightarrow B.
Let us also define |A| \leq |B| if and only if there is a 1-1 function f: A \rightarrow B. Let OP be the set of all ordered pairs of integers; i.e., OP = \{(x,y): x, y \in {\cal N} \} . Show that (a) OP is countable, and (b) |OP| \leq | \{ \mbox{all ASCII strings} \} | .

4. Let L_1 = \{ x^n y^n: n > 0\}. Let L_2 = \{z^n: n > 0\}. For each of the following strings, tell whther it is in L_1 L_2.

a. \varepsilon

b. xxyyzzy

c. xyyzz

d. xxyyzzzz

5. For each of the following languages, give a simple English description of the language, and give two strings in the language and two strings not in the language (unless the language or its complement have fewer than two strings).

a. \{ w \in \{x,y\}^* : \mbox{exactly one prefix of w ends in } y\}

b. \{ w \in \{x,y\}^* : \mbox{all prefixes of w end in } x\}

6. Get JFLAP. Create deterministic finite automata for the following four languages using JFLAP, and turn in your automata using the blackboard. There is a folder with the name Problem Set 2, you can attach and submit your .jff or zipped files through that.
The submission through this folder will close on January 20, 2012 at 12:10 PM sharp.

In all cases the alphabet is {0,1}.

1. All strings containing an even number of 1's, or exactly two 0's.
2. All strings whose length is congruent to 2 mod 3. (That is, when you divide the length by 3, you get remainder 2.)
3. All strings that are either of the form a positive number of 0's followed by a positive number of 1's, or of the form a positive number of 1's followed by a positive number of 0's.
4. All strings not containing the substring 001.

### To obtain JFLAP

Go to the website at URL http://www.jflap.org/.