Page 1 of 3

COSC 2001(A and B) 3.0—Fall 2001

Posted: Nov 19, 2001 Due: By Dec 17, 2001

Problem Set No. 3

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

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

▶ Due time: Any time on December 17, 2001. Boxes will be cleared the following morning. Location of the drop-box: There is one box— labeled 2001A and B—on the first floor of CCB, in the corridor that leads to the Ariel Lab.◀

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 #3 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 “a3partner” or anything other than “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 a3 partner”

NOT later than 5:00pm, Nov. 30, 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!

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

General Remark. Each solution must contain adequate explanation(s) of why it answers the relevant question. While examples can help us understand your point of view, they are NOT substitutes for a logical argument that establishes your solution’s validity in general.

From the text:

1. New stuff.

(a) 7.1.3, on page 271

(b) 7.1.6, on page 271

(c) 7.2.1(c), on page 280

(d) 7.2.2(a), on page 280

(e) 7.3.2(a, b), on page 292

(f) 7.4.2(b), on page 302

(g) 8.2.1(c), on page 328

(h) 8.2.2(c), on page 328

(i) Display the quintuples of the 4^{th} TM, i.e., M_{4}, in the standard enumeration M_{0}, M_{1}, M_{2}, …

(j) Recall that ϕ_{x} denotes the function of one argument computed by the Turing Machine, M_{x}, found in position x of the “standard” (lexicographic) enumeration of all Turing Machines (over a fixed input alphabet Σ). Prove that {(x, y, z) : ϕ_{x}(y) = z}, in other words,

{(x, y, z) : M_{x} with input y outputs z}

is undecidable. Hint. If the above is decidable, then so is a certain special case. Contradict this using standard diagonalization.

(k) Prove that each of the following is semi-decidable: (A) The problem 0 ∈ dom(ϕ_{x}) (B) The problem 0 ∈ ran(ϕ_{x}) Note. By “dom” we mean “domain”,

that is, for any function f of one argument

dom(f) = {x : (∃z)f(x) = z} By “ran” we mean “range”, that is, for any function f of one argument

ran(f) = {x : (∃z)f(z) = x}

2. Review questions.

(a) 4.4.2, on page 164

(b) Let a CFG G = (V, Σ, P, S) have rules of the following types only: A → Ba and A → a.

The above are templates. Thus particular instances may look like X → Xx for some variable X and constant x.

Prove by constructing a DFA that L(G) is regular. Ensure that you argue convincingly (e.g., using DFA “computations”), and generally, that the DFA works as claimed.

(c) Students do not, sometimes, believe that the Pumping Lemma goes “one way” only. Here then, to convince you once and for all:

(i) Prove that the language L over Σ = {a, b, c} given below

L = {a^{i}b^{j}c^{k} : i ≥ 0, j ≥ 0, k ≥ 0 and if i = 1 then j = k}

“can be pumped”. “Can be pumped” means exactly this: Prove that there is a positive integer p (you have to name the value that works!) such that, if z ∈ L and |z| ≥ p, then z can be decomposed as z = uvw and (a) v ≠ ε

(b) |uv| ≤ p

(c) uv^{i}w ∈ L, for all i ≥ 0. (ii) Nevertheless, prove that L is not regular!

Pause. Hmm. How does one prove L not regular if the PL does not help?

(iii) Explain why this problem does not contradict the Pumping Lemma. (iv) Is L a CFL? Prove your answer.