Solution set 1 Problem 1 function parser(in S : sentence; G : grammar; L : lexicon) return chart of edges { CHART := empty; For i = 1 to |S| do for each possible part of speech P of word S[i] in L do add edge[i-1, i, P -> S[i].] to CHART endfor endfor repeat execute one of the following two operations until no new edges can be created Matcher: pick an edge [i, j, B -> L .] in CHART; find a rule A -> B M in G; add an edge [i, j, A -> B . M] to CHART; Completer: pick an edge [i, j, B -> L .] in CHART; pick an edge [j, k, A -> M . B N] in CHART; add edge [i, k, A -> M B . N] to CHART; end repeat return CHART } (A,B are non-terminals; L, M, and N are strings of non-terminals.) Problem 2 A) i) [S [CLAUSE [NP [NP1 [noun "Jack]]] [VP [VP1 [verb "plays"] [NP [NP1 [noun "tag"]]]] "and" [VP1 [verb "catches"]] [NP [NP1 [noun "fish"]]]]]]] ii) [S [CLAUSE [NP [NP1 [noun "Jack]]] [VP [VP1 [verb "plays"] [NP [NP1 [noun "tag"]]]]]] "and" [CLAUSE [NP [NP1 [noun "catches"]]] [VP [VP1 [verb "fish"]]]]] B) One example is [0,0 NP -> NP1 "and" NP1] C) One example is [1,2, noun -> "plays"] D) One example is [2,4, NP -> NP1 "and" NP1] Problem 3 Parse tree (i) is much more likely than (ii). The best simple way to do this uses the fact that "catch" and "catches" are much more often nouns than verbs. Problem 4 Jack catches a fish: If the object is a small, moving object, then "catches" means "captures" (e.g. "catches a ball") Jack catches a cold: If the object is an infectious disease, then "catches" means "becomes ill with". Jack catches the train. If O is a mode of transportation out of A's control, then "A catches O" means that A travels via O. Jack catches sight of Jill. If the object O is a perception, then "catches O" means "perceives briefly or faintly in mode O." (e.g. "Jack caught an echo of the trumpet." "Jack caught the scent of gasoline") Jack caught the last ten minutes of Seinfeld. If the object O is (part of) an event, then "caught O" means "witnessed O". Jack caught his foot on the rug. If the object O is a part of A, then "A caught O" means that A's O was inadvertantly snagged. Of these, the second, fourth, and fifth are legitimately selectional restrictions. The first involves two properties of the object, so that is a little more complex. The third and sixth involve relations between A and O, so are not strictly selectional restrictions.