Problem Set 3

Assigned: Sept. 25
Due: Oct. 2.

Problem 1

Suppose that you are developing a program to collect events of one person meeting another from text. The output of the program will be a table of the form

Table of Meetings
Event ID Participants
101 { Mozart, Beethoven }
102 { Lincoln, Grant }
etc.

To do this, you build a compositional semantic analyzer which has the following rule among many others:

If you encounter a phrase of the form
NP1 ---> { Determiners and adjectives}
     |
     |-> Noun ---> meeting
     |
     |-> { phrases }
     |
     |-> PP ---> Prep ---> between
     |       |
     |       |-> NP2 ---> NP3 
     |                |
     |                |-> "and"
     |                |
     |                |-> NP4
     |
     |-> { phrases }
then (a) construct a new event ID, I;
(b) add a new row to the table with EventID = I and
Participants = { meaningOf(NP3), meaningOf(NP4) }

(In the above rule, entities in curly brackets are optional.)

So, for instance, suppose the program encounters the sentence, "The Atlantic Charter was negotiated at the famous meeting in August 1941 between Franklin Roosevelt and Winston Churchill aboard a warship on the coast of Newfoundland". Then the rule will match NP1 with "the famous meeting ... Newfoundland", NP3 with "Franklin Roosevelt", NP4 with "Winston Churchill".

The program will add a new row to the table [EventID=103, Participants={ Franklin Roosevelt, Winston Churchill }]

Give two examples of substantially different ways in which this rule can go wrong and can end up an invalid row for a meeting. (You may invent the example; you do not have to find examples in actual text.)

Please note: The example sentences must, of course, match the rule, and therefore the prepositional phrase "between NP3 and NP4" must modify the noun "meeting". Do not give an example where "between NP3 and NP4" comes after meeting in the sentence but does not modify it. For instance "The meeting took place some time between February and April" does not match the rule and is therefore not an example of the rule failing. However, an example where there are two syntactically possible parse trees for the sentence, one of which matches the rule, would be OK.

Problem 2

Consider the following sentence, from the New York Times, 9/22/07:
Even many hawks within the Bush administration have expressed doubts that the Syrians have the money or technical depth to build a serious nuclear program like the one in Iran.
A. Give four examples of lexical ambiguity and two examples of syntactic ambiguity in the above sentence. (The examples of lexical ambiguity must be syntactically possible; for instance it is not possible (as far as I can see) to read "like" as a verb in the above sentence, so that would not count as lexical ambiguity.)

B. Discuss how selectional restrictions can be used to resolve two of these ambiguities. Be specific about the features and constraints involved.

Problem 3

Convert the following sentences to CNF:
P <=> [Q V R].
~(P => [Q ^ R]).