Page 1 of 2

COSC 2001(A and B) 3.0—Fall 2001

Date: Sep 25, 2001 Due: Oct 16, 2001

Problem Set No. 1

Papers must be typed or word-processed (the “must” does not apply

to diagrams), and deposited to a course drop-box on the due date.

▶ Due time, and location of this box, will be announced soon by Webposting! ◀

In this Problem Set it is allowed—but not required!—to submit ONE joint paper that has a total of TWO co-authors from the same section. The same mark, as assigned to such a joint paper, will be given to each of its two authors.

▶ \underline{IFF} you are submitting Problem Set #1 with a partner, then you must notify us as described below, in items Prtnr1.–Prtnr4.:

Prtnr1. Make a file called “partner” (no quotes). [Please do not call it “Partner” or “PARTNER” or “a1partner” or anything other than just “partner”].

Prtnr2. Put in it your name and “prism” login, and the name and prism login of your partner as well.

Prtnr3. Give the following command on prism

“submit 2001 a1 partner”

NOT later than Oct. 2, 2001.

Prtnr4. Only one submission (Prtnr3., above) per pair please! ◀

If you do NOT plan to work with a partner please do NOT submit any co-author information!

(1) This teamwork is strictly for “declared” pairs, and strictly for Problem Set #1. Teamwork may not be allowed on later assignments.

(2) Any strong similarity between different papers will be seriously frowned upon. (To learn more about this issue please follow the link “Senate Policies” found on the URL: http://www.cs.yorku.ca/∼gt/courses/)

When we ask for a DFA, please design one directly (not through the NFA-to-DFA construction).

1. Design a DFA over {0, 1} that accepts exactly all the strings of length 3k+1 for some natural number^{†} k.

E.g., 0, 0110, 0000 are all in. 00, 000, 01101 are not.

2. Design a DFA over {0, 1} that accepts exactly all the strings whose digits (or “bits”) have sum equal to 3k + 1 for some natural number k.

For example, 1, 100, 1111 are in. 11, 0, 111 are not.

Hint and Requirement. Bad news first: You must prove that your automaton works. Good news: You can do that by induction. The DFA will have three states, q_{0}, q_{1}, q_{3}. If designed correctly, then the following will be true: “starting on q_{0} on an input x the DFA will halt on q_{i} iff the sum of digits of x is 3k + i (i = 0, 1, or 2).” Prove this quoted statement by induction on string length |x|. Note that you go from |x| = n to |y| = n + 1 in two ways: y = x0 or y = x1. Be mindful of the “iff”. By the way, granting that the statement is correct, q_{1} obviously is the only appropriate final state, right?

3. Text, Exercises:

(A) p.54: #2.2.3;

(B) p.67: #2.3.4(b);

(C) p.80: #2.5.3(c);

(D) p.90: #3.1.4(b);

(E) p.106: #3.2.3;

(F) p.106: #3.2.4(c);

(G) p.121: #3.4.4;

(H) p.129: #4.1.1(b,e);

(I) p.130: #4.1.2(b);

†To avoid any embarrassment, 0 is a natural number.