(1) Show all your work for computational questions. For short answer questions, make the answers
to the point, with one or two sentences maximum.
(2) Attempt any four problems out of the five. If you attempt all five, the question with the lowest
score will be dropped.
(3) You will receive score out of 80, which will be converted to out of
For example, if you receive 60 in this test, you grade will be 75.
100.
Good luck!
Problem
Points
Problem 1: Regular Patterns
20
Problem 2: Lexical Concepts
20
Problem 3: POS Tagging
20
Problem 4: Grammar Concepts
20
Problem 5: CKY Parsing
20
Total:
100
Score
Page 1 of 11
Name:
Problem 1 (20pts): Regular Patterns
Common count nouns in English use a trailing Ò to indicate the plural, e.g., cup ? cups, dog ?
dogs, or desk ? desks.
1a: FSAs (5pts)
Design a deterministic FSA that will detect whether a string matches the common noun plural
pattern.
Page 2 of 11
Name:
1b: Morphological Transducers (15pts)
Design a two-stage morphological transducer (including the lexical, intermediate, and surface
levels) to transform an input like /g +N +Pl)nto /gs The transducer should be general, i.e., it
should work with all regular singular nouns that match this pattern.
Page 3 of 11
Name:
Problem 2 (20pts): Lexical Concepts
Keep your answers short. Use at most two sentences, preferably one.
2a: Parts of Speech (5pts)
Name the two dimensions of similarity that are used to determine part of speech categories.
2b: Smoothing (5pts)
Why do we need to smooth n-gram data?
Page 4 of 11
Name:
2c: Morphotactics vs. Orthographics (5pts)
What is the difference between morphotactics and orthographics?
2d: N-grams (5pts)
Define a trigram and give two examples of NLP tasks where they can be used.
Page 5 of 11
Name:
Problem 3 (20pts): Part of Speech Tagging
Consider the following POS transition and emission tables:
NNP
VB
DT
NN
NNP
0.3
0
0.3
0
0
State #2
VB
DET NN
0.25 0.3
0.15
0.6
0
0
0
0.6
0.1
0
0
1.0
0.4
0
0.4
Emission Probabilities
0
0.4
0
0
0.2
State
State #1
Transition Probabilities
NNP
VB
DT
NN
John
1.0
0
0
0.2
Word
bit
the
0
0
0.8
0
0
1.0
0
0
dog
0
0.2
0
0.8
3a: POS Ambiguity (5pts)
Not taking into account any information about allowed state transitions, how many possible part
of speech tag sequences are there for the sentence (e dog bit John.àList each sequence.
Page 6 of 11
Name:
3b: HMM POS Tagging (15pts)
Calculate the most likely POS tag sequence for the sentence (e dog bit John. how the full
Viterbi trellis and show backpointers as arrows in the trellis, bolding those arrows representing the
best path. You may omit paths with zero probability associated with them.
Page 7 of 11
Name:
Problem 4 (20pts): Grammar Concepts
Keep your answers short. Use at most two sentences, preferably one.
4a: Grammatical Power (5pts)
Define grammatical power.
4b: Parsing Algorithms (5pts)
Apart from the usage of CNF v/s non-CNF rules, what is the main way in which CKY and Earley
parsing differ?
Page 8 of 11
Name:
4c: Syntactic Ambiguity (5pts)
Are most sentences syntactically ambiguous with a realistic grammar? Why or why not?
4d: Problems with PCFGs (5pts)
Describe two problems with PCFGs in their modeling of English, and name a solution that is
used.
Page 9 of 11
Name:
Problem 5 (20pts): CKY Parsing
Consider the following grammar:
S ?NP VP
VP ? Verb NP
VP ? Verb NP PPV
NP ? Noun
NP ? Det Noun
NP ? NP PPJ
PPV ? Prep Adverb
PPJ ? Prep Adjective
Noun ? John | dog
Verb ? chased | bit
Adverb ? vigor
Adjective ? vigor
Prep ? with
Det ? the
5a: Chomsky Normal Form (5pts)
Convert the grammar into Chomsky Normal Form. Show only the rules that are changed.
Page 10 of 11
Name:
5b: CKY Parsing (15pts)
Parse the sentence ¯hn chased the dog with vigor5sing CKY parsing. Show the parse table and
clearly indicate the backpointer links. If a symbol has multiple expansions, include multiple copies
of the symbol in the cell, distinguished by a numerical subscript, e.g., VP1, VP2; or S1, S2; etc. Draw
the parse trees that are generated by the parser.
Page 11 of 11

Purchase answer to see full
attachment