Natural Language Processing MCQ - Chomsky Normal Form CNF - What is the use?

Multiple choices questions in NLP, Natural Language Processing solved MCQ, What is the use of Chomsky normal form, CFG to CNF in CYK algorithm, CFG to CNF example

Natural Language Processing MCQ - Chomsky Normal Form CNF - What is the use?

< Previous

Next >

 

1. For parsing a sentence using CYK algorithm, the production rules of a Context Free Grammar should be in ________ normal form?

a) Backus-naur form

b) Chomsky normal form 

c) Greibach normal form

d) None of the above

 

Answer: (b) Chomsky normal form To parse a sentence, the production rules of context free grammar should be in Chomsky normal form. As per this normal form, a production rule can have on its right hand side (RHS) at most two non-terminals (variables) or a single terminal symbol or a special rule S->ε, to mark a null string. Example: Suppose {S, A, B} are non-terminals, S is the start symbol and {a, b} are terminals, then the rules can be S -> AB, or A -> a but not A -> Aa or B -> aB etc. What is the advantage of Chomsky normal form? In Chomsky Normal Form, every derivation of a string of n letters has exactly 2n − 1 steps. Thus, one can determine if a string is in the language by exhaustive search of all derivations.

 

< 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 CFG to CNF in CYK algorithm

CYK algorithm is used to parse a sentence

Syntactic parsing using CYK algorithm

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