Natural Language Processing Parsing and Syntactic Analysis 2

Question 1

The CYK (Cocke-Younger-Kasami) algorithm requires the grammar to be in which normal form?

Accepted Answer

Chomsky Normal Form

Answer

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|?

Accepted Answer

O(n³ · |G|)

Answer

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)?

Accepted Answer

A CFG where each production rule has an associated probability, and probabilities for a non-terminal sum to 1

Answer

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?

Accepted Answer

Earley's algorithm

Answer

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?

Accepted Answer

Uncertainty about which constituent a modifier or prepositional phrase should attach to

Answer

Attachment ambiguity occurs when a modifier (e.g., a prepositional phrase) can grammatically attach to more than one constituent, yielding different meanings.

Natural Language Processing Practice Test

Natural Language Processing Practice Test

Natural Language Processing Parsing and Syntactic Analysis 2