LL(k) language and not LL(k) grammar

I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language?

Grammar:

S -> a b X c d | a X f

X -> b X c | ε

You can prove by contradiction, assuming there is a value of $k$ that allows you to anticipate the sequence of derivations that is guaranteed to produce a unique tree for any input string, given some unambiguous grammar that accepts the language.

You then prove that there is a string for which a lookahead $>k$ will be needed, no matter how the grammar is constructed, because the derivation sequence is affected early in the process. A strategy similar to the pumping lemma for context-free languages comes to mind.

Incidentally, your grammar is equivalent to the following LL(1) grammar:

$\begin{align} S &\to aT \\
T &\to f \mid bXcV \\
X &\to bXc \mid \epsilon \\
V &\to d \mid f \end{align}$

Perhaps a more interesting example would be

$\begin{align} S &\to T \mid U \mid V \\
T &\to aTb \mid \epsilon \\
U &\to aUc \mid \epsilon \\
V &\to dVc \mid \epsilon \end{align}$

whose language is both not $LL(k)$ and not $RR(k)$.

StackExchange Computer Science Q#115590, answer score: 2