## CS 301, Spring 2012, Problem Set 2

- Give examples to show that:
- The intersection of two coubtably infinite sets can be finite
- or it can be countably infinite.
- The intersection of two uncountable sets can be finite,
- or it can be countably infinite,
- or it can be uncountable.

- 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.
- 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 (a) that

OP is countable, and (b) that

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 instructions that will be coming from the TA.

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

- All strings containing an even number of 1's, or exactly two 0's.
- All strings whose length is congruent to 2 mod 3. (That is, when you divide the length by 3, you get remainder 2.)
- 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.
- All strings
*not* containing the substring 001.

### To obtain JFLAP

Go to the website at URL

http://www.jflap.org/.

Follow the sidebar link labeled "Get JFLAP", and then follow the directions, ultimately downloading file jflap.jar (thick client).

Double click on the jar file to execute it.

If you run into difficulties and you are using a Mac or Linux, see either the professor or the TA. If you run into difficulties using Windows, see the TA. The professor does math, he does programming, he does computer science, he cooks, and he cleans, but *he does not do Windows!*

-- Main.sloan - 2012-01-13