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

Greibach Normal Form

Answer

Backus-Naur Form

Answer

Extended Backus-Naur Form

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

O(n)

Answer

O(n²)

Answer

O(2ⁿ)

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 CFG where rules are applied randomly

Answer

A grammar that uses neural networks to score parses

Answer

A grammar restricted to a fixed vocabulary

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

Shift-reduce parsing

Answer

Viterbi decoding

Answer

A* search

Question 5

What is 'attachment ambiguity' in NLP parsing?

Accepted Answer

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

Answer

Ambiguity caused by unknown words

Answer

Ambiguity in POS tags

Answer

Uncertainty in word segmentation

Question 6

What is the primary advantage of dependency parsing over constituency parsing for many NLP tasks?

Accepted Answer

It directly encodes head-dependent grammatical relations, making it easier to extract predicate-argument structure

Answer

It is always faster to compute

Answer

It requires no labeled training data

Answer

It handles all languages equally well

Question 7

What is a 'treebank' in the context of NLP?

Accepted Answer

A large collection of sentences annotated with syntactic parse trees

Answer

A database of word embeddings

Answer

A memory structure used during chart parsing

Answer

A set of grammar rules for a specific language