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?

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.