Page 1 of 3

COSC 2001(A and B) 3.0—Fall 2000

Date: Oct 17, 2000 Due: Nov 7, 2000

Problem Set No. 2

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

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

▶ Due time: Any time on November 7, 2000. Boxes will be cleared the following morning. Location of the drop-box: There are actually two boxes—labelled 2001A and 2001B—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 #2 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 “a2partner” 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 a2 partner”

NOT later than 5:00pm, Oct. 25, 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 #2. 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/)

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.

1. (A) 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: There is a positive integer p 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.

(B) Prove that L is not regular!

(C) Explain why this problem does not contradict the Pumping Lemma.

The above is additional evidence that you cannot use the Pumping Lemma to prove that a language is regular. L above is one that “pumps”, yet it is not regular.

2. From the text (Sipser, p.120 onwards) do:

(i) #2.2

(ii) #2.4(c, g)

(iii) #2.11

(iv) #2.14

(v) #2.17

(vi) #2.18(c)

(vii) #2.20

Erratum for 2.20: It should say “… using a derivation with ≥ 2^{b} steps, L(G) is infinite.”

3. The MATH1090 connection: Give a CFG over the alphabet

Σ = {p, 1, true, false, (, ), ¬, ⇒, ∨, ≡, ∧}

that generates all the (correctly formed) fully parenthesized Boolean expressions (also called “well-formed-formulas”).

(1) Even though we have said “fully parenthesized”, this does not mean that you must put brackets around individual variables or constants.

(2) All items in the alphabet are familiar to you. We explain here what we expect of the alphabet symbols “p” and “1”: These will be used to build the infinite supply of Boolean variables. The Boolean variables will be the strings

p1p, p11p, p111p, p1111p, …

i.e., p1^{n}p, for all n > 0, are your variables (not the “informal” ones, namely, p, q, r, p′, p′′, p′_{12}, …, that one uses in MATH1090).

4. Show that a grammar that mixes regular productions of the forms A → Ba and A → aB may produce a non-regular context free language.

(Hint. Find a simple CFG with mixed productions that generates a CFL that is known not to be regular. As always, unless your grammar obviously produces the language in question, you have to give a good general argument that it does.)