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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your time $\endgroup$
    – Shivam Gautam
    Mar 1, 2021 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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