S -> NP VPConsider the sentence "Phil drank coffee after dinner".
NP -> Noun | NP PP
VP -> Verb | Verb NP | VP PP
PP -> Prep NP
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).
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.
"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.
"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".)
"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.)
~(P V Q) => RAnswer:
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.
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:
2. AG V AH V AI.
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:
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. */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.
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 */
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.