Name: Final Exam Spring 2023, Dr. Deyaa Banisher 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. Deyaa Banisher 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. Deyaa Banisher 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. Deyaa Banisher 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. Deyaa Banisher Page 5 of 11 2c: Morphotactic vs. Orthographic (5pts) What is the difference between morphotactic and orthographic? 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. Deyaa Banisher 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 State #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 State 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. Deyaa Banisher 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 back pointers 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. Deyaa Banisher 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 Early parsing differ? Name: Final Exam Spring 2023, Dr. Deyaa Banisher 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. Deyaa Banisher 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. Deyaa Banisher 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 back pointer 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
