Page 1 of 2

COSC 2001A 3.0—Fall 2000

Posted: Nov 14, 2000 Due: TBA, after the conclusion of the current Labour dispute.

ALTERNATE Problem Set No. 2—For Section A only.

This Problem Set # 2 is for those, and only those, students who were unable to fulfil their course requirements in COSC 2000A as a result of the current Labour dispute.

It provides an alternative opportunity to complete required course work, and provides alternative extended deadlines.

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 the due date, which is TBA, after the strike. The Box will be cleared the following morning. Location of the drop-box: There is box labelled 2001A on the first floor of CCB, in the corridor that leads to the Ariel Lab.◀

In this ALTERNATIVE Problem Set it is still 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 ALTERNATE Problem Set #2 with a partner, then you must notify me (in the usual manner) 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 a2alt partner”

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!

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

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

(i) #2.4(a, d, f)

(ii) #2.6b

(iii) #2.12

(iv) #2.14

(v) #2.15

(vi) #2.16

(vii) #2.18(b)

(viii) #2.19

(ix) #2.23

2. Sipser shows in Chapter 2, Section titled “Designing Context-Free Grammars”, that a CFG with rules only of the two types A → a and A → aB (a ∈ Σ_{ε}) necessarily produces a regular language.

▶ Prove that the same is true for any CFG that exclusively has rules of the types A → a and A → Ba (a ∈ Σ_{ε}).

(Hint. Imitate Sipser’s argument to see how a DFA (or an NFA, if more convenient) can be “simulated” by such a grammar, and conversely, how a DFA might parse the strings generated by such a grammar.)

3. Prove that regular languages are closed under reversal, that is, if L is regular, then so is L^{R}, where L^{R} denotes the set of the reversals of all the strings of L.