## Mid-Term Exam: Solutions

### Problem 1 (30 points)

Consider the following CFG grammar:
S -> NP VP
NP -> Noun | NP PP
VP -> Verb | Verb NP | VP PP
PP -> Prep NP

Lexicon:
after: Prep
coffee: Noun
dinner: Noun
drank: Verb
Phil: Noun

Consider the sentence "Phil drank coffee after dinner".

A. Show two parse trees for this sentence in this grammar.

```
S ---> NP ---> Noun ---> Phil
|
|-> VP ---> Verb ---> drank
|
|-> NP ---> NP ---> Noun ---> coffee
|
|-> PP ---> Prep ---> after
|
|-> NP ---> Noun ---> dinner

S ---> NP ---> Noun ---> Phil
|
|-> VP ---> VP ---> Verb ---> drank
|       |
|       |-> NP ---> NP ---> Noun ---> coffee
|
|-> PP ---> Prep ---> after
|
|-> NP ---> Noun ---> dinner
```

B. Which of the following partial parse trees will be generated in the course of executing a recursive descent parser? (There may be more than one.)

```
i.   S ---> NP
|
|-> VP

ii.  S ---> NP
|
|-> VP ---> VP
|
|-> PP

iii. S ---> NP ---> Noun ---> "Phil"
|
|-> VP

iv.  S ---> NP ---> NP ---> Noun ---> "Phil"
|       |
|       |-> PP
|
|-> VP.
```

Answer: All but (ii).

C. Suppose that this grammar and sentence is given to a chart parser. Which of the following edges are generated? (There may be more than one.)

i. [1,1,PP -> * Prep NP]
ii. [1,1,VP --> * Verb ]
iii. [1,2, PP -> Prep * NP]
iv. [1,2, VP -> Verb * NP]

Answer: All but (iii).

### Problem 2 (20 points)

Consider the following sentence:
John made a phone call to his father and his mother.
A. Give examples of lexical, syntactic, and anaphoric ambiguity in this sentence (1 example of each category). Note: You should not give examples that will be excluded by the syntactic parser, such as the possibility that "test" is being used as a verb.

Lexical ambiguity:
"made" is ambiguous between "physically constructed" and "carried out" (and many other meanings).
"call" as a noun is ambiguous between "telephone call", "characteristic cry [call of the heron]", "personal appeal [call of the wild] [John felt a call to the priesthood]" and several others.

Syntactic ambiguity:
"and his mother" can be conjoined either with "his father" or with "phone call".
"to his father and his mother" can be attached to "phone call" or to "made".
There is a reading where "a phone call to his father and mother" is a subordinate clause, where "a phone" is the subject and "call" is the verb, meaning that John forced a telephone to call to his father and mother. (Compare "John made a canary sing to his father and mother".)

Anaphoric ambiguity:
"his" in "his mother" can refer either to John or to John's father.

B. Explain how one potential misreading of the sentence can be excluded using the techniques of ambiguity resolution that we have discussed. Be as specific as possible in your explanation.

The meaning "physically constructed" of "made" must take as its object a physical, inanimate object; hence, not "call" (nor "mother", for that matter). This is a selectional restriction.

The property "phone ..." meaning "mediated by a telephone" can only apply to a telephone call and not to the other meanings of "call" (perhaps a selectional restriction; perhaps "phone call" is just an idiom).

The possibility that "and" conjoins "phone call" and "mother" would require "mother" to be the object of "made" which we have ruled out by selectional restrictions above.

The attachment of "to" is genuinely ambiguous, but actually makes no difference to the meaning of the sentence.

The anaphoric ambiguity of "his" can only be disambiguated using parallel structure; the referent of "his mother" can be presumed to be the same as the reference of "his father". (Note that there is nothing inherantly implausible about John calling his father and his father's mother, so selectional restriction doesn't work.)

### Problem 3 (5 points)

Convert the following sentence to CNF:
~(P V Q) => R
P V R.
Q V R.

### Problem 4 (15 points)

Trace the workings of the Davis-Putnam procedure on the following set of clauses. Assume that when a choice point is reached, the algorithm makes an assignment to the first unbound atom in alphabetical order and that TRUE is attempted before FALSE.
1. A V B .
2. ~A V ~B V C V D.
3. ~A V ~C V D.
4. B V C.
5. ~B V ~D

```Let S0 be the five clauses above.
No singleton clauses, no pure literals.
Try A=TRUE. Delete 1, delete ~A from 2, 3.

Set S1:
2. ~B V C V D.
3. ~C V D.
4. B V C.
5. ~B V ~D

No singleton clauses, no pure literals.
Try B=TRUE.  Delete 4, delete ~B from 2 and 5.

2. C V D.
3. ~C V D.
5. ~D

5 is a singleton clause. Set D=FALSE. Delete 5, delete D from 2 and 3.

2. C
3. ~C

2 is a singleton clause. Set C=TRUE. Delete 2, delete ~C from 3.
3 is the empty clause.  Fail. i

Return to S1 and try B=FALSE. Delete 2, 4, delete B from 4.
3. ~C V D
4. C

4 is a singleton clause.  Set C=TRUE. Delete 4, delete D from 3.

3. D.

3 is a singleton clause. Set D=TRUE. Delete 3.
No clauses remain. The procedure succeeds with A=TRUE, B-FALSE, C=TRUE, D=TRUE.
```

### Problem 5 (10 points)

The PERFECT MATCHING problem is defined as follows: There are two sets of vertices U and V of equal size and there is a set S of edges. Each edge connects a vertex in V to a vertex U. The problem is to find a subset R of S such that each vertex in V and in U is in exactly one edge of R. (Actually, there is a polynomial time algorithm for this, but never mind that.)

For example, in the graph shown below, the edges A-H, B-G, C-I, D-J, E-L, F-K form a perfect matching.

An instance of PERFECT MATCHING can be compiled into a satisfiability problem as follows:
• The propositional atoms correspond to the edges. An atom will be assigned the value TRUE if the corresponding edge is in R. For instance, there is an atom AG that asserts that the edge A-G is in R.
• For each vertex U, for each pair of edges U-V and U-W assert that U-V and U-W are not both in R.
• For each vertex U, if U connects to V1, V2 ... Vk, then assert that one of the edges U-V1, U-V2 ... U-Vk is in R.
Give one instance of each of the two categories of constraints that would be generated for the problem shown in the diagram.

1. ~(AG^AH).
2. AG V AH V AI.

### Problem 6: (20 points)

Consider a domain where the individuals are people, books, and volumes. A volume is a physical object, made of paper and ink; a book is a work of literature, like "The Great Gatsby". Let Z be the first-order language with the following primitives:
w(P,B) --- Person P wrote book B.
r(P,B) --- Person P has read book B
c(V,B) --- Volume V is a copy of book B
o(P,V) --- Person P owns or owned volume V
e,f,g, --- Constants. Edith, Fitzgerald, The Great Gatsby.

A. Express the following statements in Z:

• i. Edith owns a copy of The Great Gatsby.
Answer: exists(V) o(e,V) ^c(V,g).
• ii. Edith has read every book that Fitzgerald wrote.
Answer: forall(B) w(f,B) => r(e,B).
• iii. Fitzgerald owned a copy of every book that he himself wrote.
Answer: forall(B) w(f,B) => exists(V) o(f,V) ^ c(V,B).
• iv. Edith has read all the books that she owns.
Answer: forall(V,B) o(e,V) ^ c(V,B) => r(e,B).

B. Let us augment the language in (A) with four further constants:

h,i,vh,vi --- Harold, Ida, Harold's and Ida's copy of The Great Gatsby respectively.
Consider the following Datalog knowledge base:
1. w(f,B) => r(h,B). /* Harold has read all the books that Fitzgerald wrote. */
2. r(h,B) => r(i,B). /* Ida has read every book that Harry has */
3. c(V,B) ^ o(i,V) => w(f,B) /* All the books that Ida owns are by Fitzgerald */
4. c(vh,g).
5. c(vi,g).
6. o(h,vh)
7. o(i,vi)
Show what happens when forward chaining is applied to this database. Your statement should show the facts that are inferred, the rules and facts that are used to infer them, and the substitution, but need not show any further details.

```Combining (3) with (5) and (7) under the substitution V-> vi, B -> g gives
(8) w(f,g).
Combining (1) with (8) under the substitution B->g gives
(9) r(h,g).
Combining (2) with (9) under the substitution B->g gives
(10) r(i,g).

No further inferences can be drawn.
```

C. Show how backward chaining can be used to infer the goal r(i,g) (Ida has read the great Gatsby.) Assume that the backward chaining follows Prolog order, as described in class.

```Goal G0: r(i,g) matches rule 2 with the substitution B->g.
Subgoal G1: r(h,g)

Goal G1: r(h,g) matches rule 1 with substitution B->g
Subgoal G2: w(f,g).

Goal G2: w(f,g) matches rule 3 with substitution B->g.
Subgoal G3: c(V,g).

Goal G3: c(V,g) matches fact 4 with substitution V->vh.
Goal G3 succeeds.

Goal G4: o(i,vh) fails.  Return to G3

Goal G3: c(V,g) matches fact 5 with substitution V->vi.
Goal G3 succeeds.

Goal G4: o(i,vi) matches fact 7. Succeeds.
Goal G2 succeeds.
Goal G1 succeeds.
Goal G0 succeeds.
```