Page 1 of 2

COSC 2001(A and B) 3.0—Fall 2000

Date: Sep 26, 2000 Due: Oct 17, 2000

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! ◀

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, Prtnr1.–Prtnr4.:

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

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

Prtnr3. Give the following command on ariel

“submit 2001 a1 partner”

NOT later than Sep. 29, 2000.

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/)

1. Define a new type of a nondeterministic automaton, M = (Σ, Q, Q_{0}, δ, F), exactly as in class/text. Except: “Q_{0}” is now—in general—not just one state, but a non-empty set of start states. Q_{0} may contain more than one state.

A string x is accepted by this model iff there is a path with label x from some state in Q_{0} to some state in F.

Prove that this model still recognizes exactly the regular languages.

2. Read carefully the definition of acceptance of a string by a DFA (p. 40, Sipser). Then prove that a DFA M accepts ε (the empty string) iff its start state is final (q_{0} ∈ F). (Note the “iff”.)

3. From the text (Sipser) do:

(A) p.84: #1.4(i)(j)(k); (B) p.84: #1.5(e)(f); (C) p.85: #1.10 [Note. Part (a) needs a general proof, while part (b)

just needs an example, a so-called “counterexample”. Choose as simple an example as you can for part (b). Part (a) does not need a proof by induction, but it DOES need a careful general proof, especially in view of the—perhaps unexpected—difference between parts (a) and (b).];

(D) p.85: #1.12(b); (E) p.86: #1.14(c) [the procedure of Lemma 1.29 must be used; do not

give an unjustified direct answer]; (F) p.86: #1.16(b)[the procedure of Lemma 1.32 must be used; do not

give an unjustified direct answer].

4. Let Σ = {0}. Which of the following languages over Σ is regular, and why?

An answer without proof is defined to be a “guess”, and is discarded.

(a) {x : |xx| is odd}

(b) {x : |x| is odd}

(c) {x : |xx| is not a prime}

(d) {x : |x| is not a prime}

(e) {x : |x| is a perfect cube}

5. For any string x over Σ = {0, 1}, let x^{R} mean its reversal (i.e., x^{R} reads right-to-left exactly as x does left-to-right).

Is {xwx^{R} : x ∈ Σ^{+} & w ∈ Σ^{+}} regular?

Why “yes” or why “no(t)”? (A proof is expected for either possible answer.)