CYK algorithm in theory of computation For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n.
Doubt: I marked it false in a national level exam.I think it should be any null-free context free grammar and not any cfg because we first have to convert cfg to cnf but only null free cfg can be converted to cnf.
Is this statement correct?
It's true.
If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar.  You already know how to do that in cubic time.
If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.