Name: Final Exam Spring 2023, Dr. Deya Banisakher Page 1 of 11 Welcome to the NLP Final Exam Please read the instructions on Blackboard

Name: Final Exam

Spring 2023, Dr. Deya Banisakher Page 1 of 11

Don't use plagiarized sources. Get Your Custom Assignment on
Name: Final Exam Spring 2023, Dr. Deya Banisakher Page 1 of 11 Welcome to the NLP Final Exam Please read the instructions on Blackboard
From as Little as $13/Page

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)

Leave a Comment

Your email address will not be published. Required fields are marked *