This is an open-book, open-notes, open-computer, open-Internet, open-library exam. It is an exam, however, so limit your discussion of it to conversations with your amiable and helpful instructor, if any.

1. Some Finite State Transducers.
   • Design an FST (call it A) to change all occurrences of "ei" to "ie". Draw A and its transition table.

   • Design an FST (call it B) to change all occurrences of "cie" to "cei". Draw B and its transition table.

   • Suppose you run A followed by B (that is, B cascaded with A) on the input "the weird theif recieved the spies". In this process, how many times must you consult either A's or B's transition table?

   • Show the diagram and transition table for the composition B o A.

   • If you run B o A on the input "the weird theif recieved the spies", how many times must you consult the transition table for B o A?

   • Why bother computing the composition B o A, when the cascade of B with A produces the same output?

2. N-grams. Consider the following punctuation-other-than-apostrophes-and-upper-case-free poem:

   	humpty dumpty sat on a wall
   	humpty dumpty had a great fall
   	all the king's horses and all the king's men
   	couldn't put humpty dumpty together again
   

   • Show the bigram counts for this poem.

   • Show the bigram probabilities (i.e. P(w2|w1)) for this poem.

   • Show the smoothed bigram counts and probabilities, using Witten-Bell smoothing.

3. The Earley Algorithm.
   • Suppose you run the Earley Algorithm (as described in the handout) on an N-word sentence. What does it mean if your chart contains a line # -> S. with (left, right) = (0,M) where M < N?

   • If you want the Earley Algorithm to recognize sentence fragments (that is, complete NP, VP, or PP) in addition to complete sentences, how would you modify the algorithm in the handout?

4. Syntax-driven Semantics. Draw a parse tree with semantic attachments for the question "Who scared my big moose?" Section 15.2 talks about how to deal with wh-questions ("who?"), genitive noun phrases ("my moose"), and adjective phrases ("big moose").