Natural Language Processing MCQ - Why do we need Chomsky Normal Form in CKY algorithm

Multiple choices questions in NLP, Natural Language Processing solved MCQ, What is the use of Chomsky normal form, CFG to CNF in CKY algorithm, Why do we need the grammar in chomsky normal form while parsing using Cocke-Kasami-Yonger CKY algorithm? CFG to CNF How to convert?

Natural Language Processing MCQ - Why we need grammar in Chomsky Normal Form in CKY algorithm?

< Previous

Next >

 

2. Why do we need our Context Free Grammar (CFG) in Chomsky Normal Form while parsing using Cocke-Kasami-Younger (CKY) algorithm?

a) Avoid ambiguity

b) Parse tree will be a binary tree

c) There is an upper bound for parsing complexity 

d) All of the above

 

Answer: (d) All of the above When do we say that a grammar in chomsky normal form? A CFG is in Chomsky normal form when every rule is of the form A → BC and A → a, where a is a terminal, and A, B, and C are variables. Further B and C are not the start variable. Additionally we permit the rule S →ε where S is the start variable.   Some reasons for using CNF Parse trees for a derivation using Chomsky normal form will be a binary tree. The use of Chomsky normal form instead of CFG, helps to avoid ambiguity problem during parsing. In Chomsky normal form, every derivation of a string of length n has exactly 2n-1 steps. One can determine if a string is in the language by exhaustive search of all derivations.   Why Chomsky Normal Form in CKY algorithm? The CKY can be performed in cubic time: O(n3), where n is the number of words in the sentence. The runtime of CYK depends on the length of the longest production rule, since the algorithm considers all possible ways of decomposing a string into k parts for a production of length k. This means that the runtime per phase is O(nk), where k is the length of the longest production. Since there are O(n) phases, the runtime of CYK on a grammar with maximum production length k is O(nk+1).

 

< Previous

Next >

******************

Related links:

• Go to Natural Language Processing home page

• Go to Natural Language Processing - Glossary

• Go to NLP - MCQ Quiz Home page

Top interview questions in NLP

NLP quiz questions with answers explained

What is the use of chomsky normal form

Why do we need to convert the grammar in CFG to CNF in CKY algorithm

CKY algorithm is used to parse a sentence

Syntactic parsing using CKY algorithm required binary grammar

Why does CKY algorithm require the input grammar in binary form?

Why do we expect the input grammar to CKY in Chomsky normal form?

NLP Solved MCQ, Natural language processing solved mcq, language model solved mcq, perplexity solved mcq, nlp solved exercises