Page 1 of 3

COSC 2001(A and B) 3.0—Fall 2001

Date: Oct 27, 2001 Due: Nov 20, 2001

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 20, 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 #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 “prism” login, and the name and prism login of your partner as well.

Prtnr3. Give the following command on prism

“submit 2001 a2 partner”

NOT later than 5:00pm, Nov. 10, 2001s.

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.

From the text:

1. 4.2.6 (b, c), p.147

2. 4.3.5, p.154

3. 5.1.3, p.180

4. 5.2.1, p.191

5. 5.2.2, p.191

6. 6.2.2 (b), p.236

7. 6.3.2, p.245

8. 6.3.5 (c), p.246

9. The MATH 1090 Connection. In the MATH 1090 text (Gries and Schneider) it is described, but not formally defined, what the syntax of Predicate Calculus formulas is.

We would like you to define a CFG whose language is the set of all the formulas of Predicate Calculus for Arithmetic.

As you recall, each application of Predicate Calculus to a specific branch of Mathematics, like Arithmetic over the natural numbers ℕ = {0, 1, 2, …}, has the need of special symbols—which most logicians call “nonlogical symbols”.

In our case these special symbols are:

(a) 0. Comment. A constant symbol. If interpreted, this stands for the number 0.

(b) S. Comment. A function symbol of arity 1.^{†} If interpreted, S(x) stands for x+1. Using S and 0 we can denote all the remaining natural numbers, so we do not need any other constant symbols beyond 0 in the alphabet. E.g., S(0) denotes “1”, S(S(0)) denotes “2”, etc.

(c) +. Comment. A function symbol of arity 2. If interpreted, x + y stands for x + y.

(d) ×. Comment. A function symbol of arity 2. If interpreted, x × y stands for x × y.

(e) <. Comment. A predicate symbol of arity 2. If interpreted, x < y stands for x < y.

†“Arity” is the number of required arguments for the function or predicate symbol.

We also have the usual required symbols for logic (so-called logical symbols), namely “=” (equals; not to be confused with “≡” which we leave out), “∃” (we leave “∀” out), “¬”, “∨”, brackets—that is, “(” and “)”—and variables: of Boolean type, p_{1}, p_{2}, p_{3}, … and of integer (natural number) type, v_{1}, v_{2}, v_{3}, … We also have the two Boolean constants, denoted by “false” and “true” in the text by Gries and Schneider. Here we will denote them by the “one character” symbols “⊥” and “⊤” respectively.

The task is to define a CFG (in BNF) with start symbol called ⟨wff⟩ such that

⟨wff⟩ ⇒^{∗} x iff x is some Predicate Calculus formula (for Arithmetic)

Your grammar will need other nonterminals as well, at the very least, ⟨term⟩, ⟨Bvar⟩ and ⟨Nvar⟩ so that

⟨term⟩ ⇒^{∗} x iff x is some Predicate Calculus term^{†}

⟨Bvar⟩ ⇒^{∗} x iff x is some Predicate Calculus Boolean variable, p_{i}

and

⟨Nvar⟩ ⇒^{∗} x iff x is some Predicate Calculus natural number variable, v_{i}

The latter two take care of the requirement that the alphabet is finite. Thus, p_{i} is really the string

p \underbrace{| … |}_{i of |} p

and v_{i} is really the string

v \underbrace{| … |}_{i of |} v

To sum up, here is the alphabet A of terminal symbols:

A = {⊥, ⊤, v, p, |, (,), =, ∃, ¬, ∨, 0, S, +, ×, <}

The nonterminal alphabet is partly: V = {⟨wff⟩, ⟨term⟩, ⟨Bvar⟩, ⟨Nvar⟩}.

Your task: Complete V—if needed—and give the productions so that

the grammar is unambiguous. Explain clearly (not “by example”) why your grammar IS unambiguous.

Caution. Please do not say “it is unambiguous because every string in the language has a unique leftmost derivation”. This just states the definition of “unambiguous”. The question is, why do you think that your grammar is such that “every string in the language has a unique leftmost derivation”?

†Recall that, recursively speaking, a “term” is a variable or a constant, or is an application of a function symbol on the correct number of term-arguments.