HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Determining whether a CFG is $LL(k)$ for any $k$?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
determininganycfgforwhether

Problem

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?

Solution

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'$.

Context

StackExchange Computer Science Q#2889, answer score: 5

Revisions (0)

No revisions yet.