## 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.
- More math pencil and paper problems coming after I figure out how to get math notation on this wiki!

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

Topic revision: r2 - 2012-01-15 - 01:15:27 - Main.sloan