CS 395
Midterm
Ondich
Due on paper 8:30 PM Friday, April 27, 2001
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.
- 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?
- 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.
- 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?
- 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").