Assigned Wednesday 4/4/01. Due midnight Wednesday 4/11/01.
N-Grams.
Assigned Friday 4/13/01. Due on paper at class time Wednesday 4/18/01.
Using the grammar from the example handed out in class Friday,
do the following:
Create a syntactically ambiguous sentence whose ambiguities
can be expressed by the rules in the given grammar.
Add whatever words your sentence requires to the appropriate
lexical categories.
Step through the Earley algorithm for your sentence, generating
a parse chart for your sentence.
Describe an algorithm for taking a completed Earley algorithm
chart and using it to draw the constituent trees of the various
parses discovered by the algorithm.
On page 4 of Jurafsky and Martin, there are five interpretations
of the sentence "I made her duck." Draw parse trees for each
of these interpretations.
What rules and vocabulary need to be added to our example grammar
to accomodate the "I made her duck" parse trees?
In addition, do the following:
Find the WordNet project, the Penn Treebank project, and the
Switchboard corpus on the web. Write a brief description of what
each of these things is for, and what tools are provided by the projects.
Give web references.
Look for open-source parsers. If you find any, include references
to them.
Exercises to try, but not to hand in
Design two FST's to do the following to an input string:
FST1: Change all occurrences of "ei" to "ie".
FST2: Change all occurrences of "cie" to "cei".
Then, generate and simplify the composition FST2 o FST1.
Based on a corpus consisting of the words to "Hickory Dickory Dock,"
create the count and probability tables for unsmoothed bigrams.
Then smooth them using add-1, Witten-Bell, and Good-Turing smoothing.
Suggested Reading
3/26/01. Read the Preface and Chapters 1, 2, and 3
of Jurafsky and Martin. Chapter 1 is largely background information,
and Chapter 2 is an in-context review of material you should
know from Theory of Computation (or, possibly, a linguistics
course or two). In Chapter 3, pay particular attention to
understanding how Finite State Transducers work.
4/4/01. Read Chapter 6.
4/11/01. Read Chapter 10. You might find the ideas in
Chapter 10 easier to deal with if you skim Chapter 9 first.