Ling/CSE 472: Assignment 4: PCFGs, Reference Resolution

Due November 18th, by the start of class, consists of 3 parts

Part 1: Probabilities assigned to trees

Find two sentences licensed by the grammar on slide 5 of 11/4, such that the longer sentence has a higher probability than the shorter sentence. Show the trees assigned to each sentence by the grammar, with a probability on each node, and the probability of each tree.

[NB - This grammar is just like the one in Fig 12.1 (p.449), except that the probability for Proper-Noun -> Denver has been corrected to .60.]

Part 2: Probabilistic parsing

Step through the corrected version of the pseudocode for probalisitic CKY (see slide 11 of 11/4) to see how it would parse the following sentence, given this grammar:

Kim adores snow in Oslo.

Your write-up should include two things:

• A diagram showing the final state of the chart
• A list of edge descriptions in the order in which the edges were added to chart. Each edge description should indicate the rule that licenses it, its span, and its probability.

We recommend using a format like the following for displaying the chart: (NB - This figure is intended solely to illustrate the display method and bears no ressemblance to the chart for the sentence you are considering.)   

	1	2	3
1	Nom: .004 N: .08		S: .0008
2	VP: .0001 V: .09	VP: .003
3		NP: .01 Nom: .05 N: .08

Hint: The counter m in the second to inner-most loop is what determines the order in which the two possible VPs will be considered.

Part 3: Reference resolution

Do problems 18.3 and 18.4 on p.716 of the textbook.