Showing posts with label CYK algorithm. Show all posts
Showing posts with label CYK algorithm. Show all posts

Sunday, February 20, 2022

Natural Language Processing MCQ - 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?

Natural Language Processing MCQ - What is not CKY algorithm

< Previous                      

Next >

 

1. Which of the following is/are true about CKY algorithm?

a) It requires that the grammar be in Chomsky Normal Form (CNF)

b) Only the intermediate solutions that contribute to a full parse tree are further processed 

c) CKY is a top-down parsing algorithm

d) CKY is a naïve search algorithm

 

Answer: (a) It requires that the grammar be in Chomsky Normal Form (CNF) and (b) Only the intermediate solutions that contribute to a full parse tree are further processed

 

(a) The use of Chomsky normal form instead of CFG, helps to avoid ambiguity problem during parsing. The time complexity of CKY algorithm is O(n3) where n is the number of words in the given sentence. Using the grammar which is in CNF reduces the complexity caused due to the longer production rules. Because production rules as per CNF are of binary form at the maximum. Refer here for more.

 

(b) CKY uses dynamic programming. Hence, intermediate solutions are stored. And these intermediate solutions only need to be pursued further for parsing the input sentence.

 

CKY is a bottom-up parsing algorithm.



< Previous                      

Next >


******************
Related links:



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

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery