Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable.

Is there a similar result showing that it is undecidable whether a given CFG is an $LL(k)$ grammar for some choice of $k$? Or is this problem known to be decidable?

share|cite|improve this question
I know that the $LL(1)$ property can be checked. See these slides (48++). Have you tried adapting Knuth's proof to $LL$? – Raphael Jul 27 '12 at 22:54
up vote 5 down vote accepted

This is undecidable. It is theorem 11 in Properties of deterministic top down grammars by Rosenkrantz and Stearns. Theorem 12 in the same paper however states that the problem becomes decidable if the grammar is known to be $LR(k')$ for some (possibly different) $k'$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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