This is an open-book, open-Internet, open-library takehome exam. You may not consult with any person other than Jeff Ondich about this exam.
Several of the questions on this exam concern a tiny grammar and lexicon restricted to the domain of Ernie's breakfast.
Run the Earley algorithm on the sentence "Ernie eats a pancake." Show me the resulting chart.
How many lines of the form "# -> S ." does your chart contain? Explain what they mean.
Give three word sequences that are accepted by our grammar/lexicon/algorithm but that are not grammatically correct English sentences.
How can you modify the Earley algorithm as presented in class so as to recognize any S, NP, or VP? For example, if you want the algorithm to accept "Ernie eats a pancake," "eats a pancake," and "a pancake," what do you do? (Hint: This requires a very simple change.)
After the fashion of the syntax-driven semantic analysis presented in Chapter 15, show semantic attachments for each of the rules in our grammar and lexicon. Then, show the parse tree for "Ernie eats a big pancake" with semantic attachments next to each of the non-terminal constituents in the tree. These attachments should reflect not just the rule whose left side is the constituent in question, but rather the semantic description of the entire subtree rooted at the constituent. (When I presented this material in class, I showed two copies of the same tree. The first just showed the FOPC expressions taken straight from the grammar and lexicon. The second tree showed the FOPC expressions that you build by composing the expressions from the bottom up. I want you to show me the second of these trees. If this is not clear, please ask me about it in class Wednesday.)
I want to add the adverb "slowly" to our lexicon, to allow Ernie to take his time over breakfast. What rules and semantic attachments should I add to the grammar and lexicon to support this adverb?
(3 points) I like to keep track of American pop culture a little bit, even though there's really no hope of my keeping up with or understanding it. Still, I'd like you to humor me by telling me what you think I should read or watch or listen to if I want to know what's happening in Popland these days.
If you're in my CS207 class, you have to tell me something different here. No double-dipping when it comes to my education.
Suppose we want to model the difference between mass nouns and count nouns ("some food" vs. "three pancakes") using feature structures and unification. Our goal in the context of Ernie's breakfast is to prevent "Ernie eats pancake" and "Ernie eats a food" from being accepted.
Add suitable feature structures to the grammar and lexicon. Note that you will not need to add feature structures to every rule.
Show the parse trees for "Ernie eats a pancake" and "Ernie eats pancake" with unified feature structures drawn next to each constituent in the tree. Again, this is the tree where all the unification operations have been performed from the bottom up, rather than a simple labeling of the non-terminals with their associated feature structures from the grammar and lexicon. Note that some constituents will have no feature structure, while some may be labeled "failure to unify" or something like that.
Imagine a word sequence w1 w2 w3...wn. The probability that this sequence occurs can be described by the equation:
P(w1 w2...wn) = P(w1) P(w2|w1) P(w3|w1 w2) ... P(wn|w1 w2...w(n-1))
This equation is not an approximation--it's a consequence of the rules of probability.
Suppose we use a trigram language model to approximate this probability. To do so, we have to make an assumption about the conditional probabilities in the formula above. What assumption do we have to make? What simplified formula results from our assumption?
It is common to compute log P(w1 w2...wn) instead of P(w1 w2...wn). Why?
Many of you added logs of probabilities to measure likelihoods in the author-identification assignment. Others of you just added the probabilities themselves. Explain why I did not (and still do not) like the latter approach.
Use the poem Richard Cory, by Edwin Arlington Robinson, as a corpus to train your trigrams. Ignore punctuation and capitalization. Now compute P( "and he was always" ) using this model.