# Probabilistic CKY Assignment

Below we give the CKY chart for a parse of the 10-word sentence:

The agency sees use of the codes as a way.

The assignment is to assign probabilities to each of the edges used in the 5 parses the example sentence has using the probabilities in the Probabilistic CF grammar below. You do not have to assign probabilities to edges not used in any of the 5 parses. You will find it helpful to use the solution to the last assignment as a guide to make sure you are considering all possible ways of building each edge.

What you need to hand in is a version of the chart below that has the Viterbi values associated with each edge in the chart used in one of the 5 parses. and your calculations. For example, a four word sentence chart might look like the chart below, using the grammar below:

 1the 2 agency 3 sees 4 codes 0 dt, .5 np, .0025 s, .0001 1 n, .01 nbar, .01 2 vbz, 1.0 vp, .004 2 n, .01nbar, .01

We first give the grammar the parser uses (in Chomsky Normal Form), as well as the lexicon.

## Probabalistic Context Free Grammar

```pp -> p np, 1.0
vpg -> vbg np, 1.0
X2 -> X1 pp, 1.0
vp -> vbz np, .4
vp -> X1 pp, .5
vp -> X2 pp, .1
ap -> rb a, 1.0
s -> np vp, 1.0
np -> dt nbar, .5
np -> X3 np, .1
np -> ap nbar, .05
np -> nbar pp, .2
np -> n n, .05
np -> vbg np, .05
X3 -> np cc, 1.0
X1 -> vbz np, 1.0
nbar -> ap nbar, .1
nbar -> nbar pp, .3
nbar -> n n, .5
nbar -> vbg np, ..05
```

## Lexicon

```a: dt, .5
and: cc, 1.0
use: n,.01; np,01; nbar.01
codes: n,.01; np,01; nbar,.01
sees: vbz,1.0
of: p,.5
agency: n,.01; np,.01; nbar,.01
rapidly: rb,1.0
handling: vbg,.5
labor: n,.01; np,.01, nbar
as: p,.5
costs: n,.01; np,.01 nbar,.01
controlling: vbg,.5
way: n,.01; np,.01; nbar,.01
growing: a,.5 ap,.5
the: dt,.5
```

k
 1the 2 agency 3 sees 4 use 5 of 6 the 7 codes 8 as 9 a 10 way 0 dt np s s s 1 npnbarn s s s 2 vbz vpX1 vpX2X1 vpX2X1 3 npnbarn npnbar npnbar 4 p pp pp 5 dt np np 6 npnbarn npnbar 7 p pp 8 dt np 9 npnbarn