Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 1 of 11
Welcome to the NLP Final Exam
Please read the instructions on Blackboard carefully before beginning the exam. You will need
to scan and upload this exam to Blackboard within the allocated time for your exam to be
graded.
(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 100.
For example, if you receive 60 in this test, you grade will be 75.
Good luck!
Problem Points Score
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
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 2 of 11
Problem 1 (20pts): Regular Patterns
Common count nouns in English use a trailing s 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.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 3 of 11
1b: Morphological Transducers (15pts)
Design a two-stage morphological transducer (including the lexical, intermediate, and surface
levels) to transform an input like dog +N +Pl into dogs. The transducer should be general, i.e.,
it should work with all regular singular nouns that match this pattern.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 4 of 11
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?
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 5 of 11
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.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 6 of 11
Problem 3 (20pts): Part of Speech Tagging
Consider the following POS transition and emission tables:
Transition Probabilities
State #2
NNP VB DET NN
St
at
e
#1
0.3 0.25 0.3 0.15 0
NNP 0 0.6 0 0 0.4
VB 0.3 0 0.6 0.1 0
DT 0 0 0 1.0 0
NN 0 0.4 0 0.4 0.2
Emission Probabilities
Word
John bit the dog
St
at
e
NNP 1.0 0 0 0
VB 0 0.8 0 0.2
DT 0 0 1.0 0
NN 0.2 0 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 The dog bit John.? List each sequence.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 7 of 11
3b: HMM POS Tagging (15pts)
Calculate the most likely POS tag sequence for the sentence The dog bit John. Show 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.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 8 of 11
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?
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 9 of 11
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.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 10 of 11
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.
Name: Final Exam
Spring 2023, Dr. Deya Banisakher Page 11 of 11
5b: CKY Parsing (15pts)
Parse the sentence John chased the dog with vigor using 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.
End of exam
Problem 1 (20pts): Regular Patterns
1a: FSAs (5pts)
1b: Morphological Transducers (15pts)
Problem 2 (20pts): Lexical Concepts
2a: Parts of Speech (5pts)
2b: Smoothing (5pts)
2c: Morphotactics vs. Orthographics (5pts)
2d: N-grams (5pts)
Problem 3 (20pts): Part of Speech Tagging
3a: POS Ambiguity (5pts)
3b: HMM POS Tagging (15pts)
Problem 4 (20pts): Grammar Concepts
4a: Grammatical Power (5pts)
4b: Parsing Algorithms (5pts)
4c: Syntactic Ambiguity (5pts)
4d: Problems with PCFGs (5pts)
Problem 5 (20pts): CKY Parsing
5a: Chomsky Normal Form (5pts)
5b: CKY Parsing (15pts)
