Natural Language Processing Parsing and Syntactic Analysis 2 — Questions and Answers
Question 1: The CYK (Cocke-Younger-Kasami) algorithm requires the grammar to be in which normal form?
- Greibach Normal Form
- Chomsky Normal Form (Correct answer)
- Backus-Naur Form
- Extended Backus-Naur Form
Correct answer: Chomsky Normal Form
CYK requires Chomsky Normal Form (CNF), where every rule is either A → BC or A → a, enabling dynamic programming over spans.
Question 2: What is the time complexity of the CYK parsing algorithm for a sentence of length n with a grammar of size |G|?
- O(n)
- O(n²)
- O(n³ · |G|) (Correct answer)
- O(2ⁿ)
Correct answer: O(n³ · |G|)
CYK runs in O(n³ · |G|) time because it fills an n×n triangular table by considering all possible split points for every span.
Question 3: What is a probabilistic context-free grammar (PCFG)?
- A CFG where rules are applied randomly
- A CFG where each production rule has an associated probability, and probabilities for a non-terminal sum to 1 (Correct answer)
- A grammar that uses neural networks to score parses
- A grammar restricted to a fixed vocabulary
Correct answer: A CFG where each production rule has an associated probability, and probabilities for a non-terminal sum to 1
A PCFG augments each CFG rule with a probability so that the parser can rank alternative parse trees by their overall probability.
Question 4: Which algorithm can parse ALL context-free grammars (not just CNF) and runs in O(n³) time?
- Shift-reduce parsing
- Earley's algorithm (Correct answer)
- Viterbi decoding
- A* search
Correct answer: Earley's algorithm
Earley's algorithm handles any CFG without requiring normal form conversion and operates in O(n³) time in the general case.
Question 5: What is 'attachment ambiguity' in NLP parsing?
- Ambiguity caused by unknown words
- Uncertainty about which constituent a modifier or prepositional phrase should attach to (Correct answer)
- Ambiguity in POS tags
- Uncertainty in word segmentation
Correct answer: Uncertainty about which constituent a modifier or prepositional phrase should attach to
Attachment ambiguity occurs when a modifier (e.g., a prepositional phrase) can grammatically attach to more than one constituent, yielding different meanings.
Question 6: What is the primary advantage of dependency parsing over constituency parsing for many NLP tasks?
- It is always faster to compute
- It directly encodes head-dependent grammatical relations, making it easier to extract predicate-argument structure (Correct answer)
- It requires no labeled training data
- It handles all languages equally well
Correct answer: It directly encodes head-dependent grammatical relations, making it easier to extract predicate-argument structure
Dependency parses make grammatical relations (subject, object, modifier) explicit, which is directly useful for information extraction and semantic analysis.
Question 7: What is a 'treebank' in the context of NLP?
- A database of word embeddings
- A large collection of sentences annotated with syntactic parse trees (Correct answer)
- A memory structure used during chart parsing
- A set of grammar rules for a specific language
Correct answer: A large collection of sentences annotated with syntactic parse trees
A treebank is a corpus in which sentences have been manually annotated with syntactic structures, used to train and evaluate parsers.
Natural Language Processing Parsing and Syntactic Analysis 2
The CYK (Cocke-Younger-Kasami) algorithm requires the grammar to be in which normal form?