## Problem Set 1

Assigned: Sept. 24
Due: Oct. 8

1. Write an algorithm for a bottom-up chart parser. You should use the same form of edges as in the book's algorithm, but construct the edges working up from the words of the sentence to the root of the tree. You may assume that no rules have an empty right-hand side.

2. Consider the following fragment of English grammar:

S -> CLAUSE
S -> CLAUSE "and" CLAUSE
CLAUSE -> NP VP
NP -> NP1
NP -> NP1 "and" NP1
NP1 -> proper_noun
NP1 -> noun
VP -> VP1
VP -> VP1 "and" VP1
VP1 -> verb
VP1 -> verb NP
and the following lexicon:
Jack: proper_noun
plays: noun, verb
tag: noun, verb
catches: noun, verb
fish: noun, verb

Consider parsing the sentence "Jack plays tag and catches fish."

• A) Show the two parse trees for this sentence in this grammar.
• B) Give an example of an edge that will be constructed in a top-down parse but not in a bottom-up parse.
• C) Give an example of an edge that will be constructed in a bottom-up parse but not in a top-down parse.
• D) Give an example of an edge that will be constructed both in a top-down parse and in a bottom-up parse, but is not part of either parse tree.

3) One of the parse tree in (2A) is very much more plausible than the other. Describe a simple method for choosing the preferred tree.

4) (Open-ended) Even if "catches" is correctly identified as a transitive verb, it has a number of different meanings:

Jack catches a fish.
Jack catches a cold.
Jack catches the train.
Jack catches sight of Jill.
Jack caught the last ten minutes of Seinfeld.
Jack caught his foot on the rug

Discuss the use of selectional restrictions in finding the correct interpretation of each of these sentences. For each of these, you should propose a rule that will be satisfied by the correct interpretation. Try to formulate your rule at a reasonably general level, and give one or two other examples of sentences where the rule applies. If you do not think that selectional restrictions are a suitable technique for the example, explain why not and propose another method.

Note: Finding the "best" level of generality is by no means easy. For instance, one can say

1) Jack catches the train to New York every morning.
2) Jack takes the bus to New York every morning.
3) Jack takes his car to New York every morning.

But you cannot say:

4) * Jack catches his car to New York every morning.

It would be difficult or impossible to propose a single rule that will include (1), (2), and (3) but will exclude (4). So your rule for (1) must either exclude (2), despite their apparent similarity, or must include (2) but exclude (3), despite their apparent similarity.