0
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your time $\endgroup$ – Shivam Gautam Mar 1 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.