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?


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

X -> b X c | ε

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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