Question

The standard version of CYK algorithm operates only on context free grammars in the following form:

(a) Greibach Normal form

(b) Chomsky Normal form

(c) Backus Naur form

(d) All of the mentioned

I had been asked this question in final exam.

My enquiry is from CFL- Other Normal Forms in section Properties of Context Free Languages of Automata Theory

Answer 1

Correct option is (b) Chomsky Normal form

The explanation: It requires the presence of a context free grammar into Chomsky Normal form to operate. However, every context free grammar can be converted into CNF for keeping the sense of grammar equivalent.