Homework 8

  1. This first exercise provides an opportunity to make sure you understand the CKY (also known as CYK) recognition algorithm. I'm providing an implementation of the algorithm as a way for you to check whether or not you're doing it correctly. This means there is no excuse for turning in incorrect answers! (Feel free to do your own implementation if you prefer the extra programming experience.) Note, that if you just copy the answers given by the program, you won't know how to do it yourself, which could conceivably hurt you if we include a question about this on the final exam...

  2. Using the PCFG in Figure 12.1, show in detail how to compute the probability for the sentence the flights include a book.

  3. Add the rules Noun --> books and Verb --> books to the grammar in Figure 12.1. Assuming this revised grammar, is the sentence TWA books flights locally ambiguous, globally ambiguous, both, or neither? Explain clearly.

  4. Jurafsky and Martin, 14.6

  5. Jurafsky and Martin, 14.8

  6. Optional. For those interested in exploring probabilistic CFGs a bit further, use anonymous ftp to umiacs.umd.edu to download pub/resnik/ling645/pcfg.tar.gz, uncompress it, etc. This is an implementation of PCFG training written by Mark Johnson of Brown University, kindly made available for research purposes. Read the README file, run the toy examples for yourself, and note how, even though the grammar allows multiple word orders for VPs, the probabilities for the different rules depend on whether you train on sentences with English word order or with German word order.

    Some other things to try: