G22.2590 Natural Language Processing Spring 2003

The final exam

The questions will be taken from the following list of question types. All have been given for homework except #10. I may also ask one short (1-page) essay question about one of the issues we have discussed in the lectures.

  1. English sentence structure: Label the constituents (NP, VP, PP, etc.) of an English sentence based on the grammar given in Chapter #9. If the sentence is ambiguous, show its multiple parses. If the sentence violates some grammatical constraint, describe the constraint. (homework #2).
  2. Context-free grammar: Extend the context-free grammar to cover an additional construct, or to capture a grammatical constraint. (homework #2).
  3. Parsing: Given a very small context-free grammar, to step through the operation, or count the number of operations performed by a top-down backtracking parser, a bottom-up parser, or a chart parser (homework #3).
  4. POS tagging: Tag a sentence using the Penn POS tags (homework #3).
  5. HMMs and the Viterbi decoder: Describe how POS tagging can be performed using a probabilistic model (J&M sec. 8.5; lecture 4 notes). Create an HMM from some POS-tagged training data. Trace the operation of a Viterbi decoder. (homework #4).
  6. Feature grammar: Augment a context-free grammar using the feature formalism of J&M 11.3 to capture a grammatical constraint (homework #5).
  7. Probabilistic CFG: Train a probabilistic CFG from some parses; apply this PCFG to disambiguate a sentence (homework #7). Explain how this PCFG can be extended to capture lexical information.
  8. Logical form: write the logical form of an English sentence, with or without event reification (homework #8).
  9. Semantic interpretation: Draw a tree for a sentence using J&Ms Chap. 15 grammar with semantic features. Add a rule to this grammar. (homework #10).
  10. Anaphora: be able to explain the constraints and preferences involved in the resolution of an example of noun phrase anaphora.
  11. Jet: be able to extend, or trace the operation, of one of the Jet pattern sets we have distributed and discussed (for noun and verb groups, and for appointment events).