ProblemSet2 < CS301

CS301 Web>Syllabus>Homeworks>ProblemSet2 (2012-01-18, Main.sloan) (raw view)EditAttach
---++ CS 301, Spring 2012, Problem Set 2
   1 Give examples to show that: 
      1 The intersection of two coubtably infinite sets can be finite
      1 or it can be countably infinite.
      1 The intersection of two uncountable sets can be finite,
      1 or it can be countably infinite,
      1 or it can be uncountable.
   1 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 <latex> {\cal N} = \{0, 1, 2, \ldots \} </latex> to the set of all squares of nonnegative integers.
   1 In class and in the Sipser book, we defined <latex>|A| = |B|</latex> if and only if there is a 1-1 onto function <latex>f: A \rightarrow B</latex>.
Let us also define <latex> |A| \leq |B|</latex> if and only if there is a 1-1 function <latex>f: A \rightarrow B</latex>. Let <latex>OP</latex> be the set of all ordered pairs of integers; i.e., <latex>OP = \{(x,y): x, y \in {\cal N} \} </latex>. Show that (a) <latex>OP</latex> is countable, and (b) <latex>|OP| \leq | \{ \mbox{all ASCII strings} \} | </latex>.

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

a. <latex>\varepsilon</latex>

b. <latex>xxyyzzy</latex>

c. <latex>xyyzz</latex>

d. <latex>xxyyzzzz</latex>

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. <latex> \{ w \in \{x,y\}^* : \mbox{exactly one prefix of w ends in } y\} </latex>

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

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. <br />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.
   1 All strings whose length is congruent to 2 mod 3. (That is, when you divide the length by 3, you get remainder 2.)
   1 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.
   1 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: r6 - 2012-01-18 - 00:34:36 - Main.sloan
CS301
[edit this menu]
WISEST
Helping Women Faculty Advance
Funded by NSF