Looking for a language that is not LL (1)?

Question

I played with a lot of grammars that were not LL (1) recently, and many of them can be converted to grammars that are LL (1).

However, I have never seen an example of a unique language that is not LL (1). In other words, a language for which any unambiguous grammar for a language is not LL (1)), and I don’t know how I could prove that I found it if I accidentally stumbled upon it.

Does anyone know how to prove that a particular explicit language is not LL (1)?

Answer 1

I thought about this question for a while, and then found this language on Wikipedia :

S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | ε 

They argue that the language described above cannot be described by LL (k) grammar. You asked only about LL (1), and it is quite simple. Having only the first character, you do not know if the sequence is “ab” or “aab” (or more recursive), and therefore you cannot choose the correct rule. Thus, the language is definitely not LL (1).

Also, for each sequence generated by this grammar, there is only one derivation tree. Therefore, the language is unambiguous.

The second part of your question is a bit more complicated. It is much easier to prove that the language is LL (1) than the opposite (there is no LL (1) grammar describing the language). I think you are just creating a grammar describing the language, then you are trying to do this LL (1). Once you find a conflict that cannot be resolved, you must somehow use it and create evidence.