# 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 | ε

• Is your not LL(k) grammar context-free? – André Souza Lemos Oct 8 at 18:30
• yes, it's context-free. I can post it, but I want solve that myself – J j Oct 8 at 18:44
• How do you know that it's not LL(k)? – André Souza Lemos Oct 8 at 18:48
• I test grammar on some words from this language – J j Oct 8 at 18:55
• I can't explain clearly, so I post grammar – J j Oct 8 at 19:08

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