Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Question

Consider the language $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements.

$\quad\quad\text{I. }L$ is deterministic context-free.
$\quad\quad\text{II. }L$ is context-free but not deterministic context-free.
$\quad\quad\text{III. }L$ is not $LL(k)$ for any $k$.

Which of the above statements is/are TRUE?

$\quad\quad\quad$ A. $\text{I}$ only
$\quad\quad\quad$ B. $\text{II}$ only
$\quad\quad\quad$ C. $\text{I}$ and $\text{III}$ only
$\quad\quad\quad$ D. $\text{III }$ only

(GATE-CS-2020)

My doubt is only regarding a part of the above question, i.e. arguing about statement $\text{III}$.

Most of my mates are arguing as :

"Since $a^n$ for any arbitrary $n$, on just seeing $a^n$ on the input we cannot decide whether it is a part of $a^m$ or $a^mb^m$ for $m>n$ so the language is not $LL(k)$ for any $k$ since we cannot have an arbitrary or finite $k$ ".

But while reading the automata text by Peter Linz I came across an example as:

Example 7.11 The grammar $$S \rightarrow SS |aSb| ab$$ not an $LL (k)$ grammar for any $k$.

The above grammar in the Linz text is the grammar generating the positive closure of $\{a^nb^n|n\geq 1\}$ or simply it generates the set of strings having well formed parenthesis structure.

Now here the thing to be noted is that : Linz talks about the "grammar" not about the language as a whole. Talking about the language seems a bit difficult to me.

The author says that the "grammar" is not $LL(k)$ for any $k$ with the following argument:

To see why this is so, look at the derivation of strings of length greater than two. To start, we have available two possible productions $S \rightarrow SS$ and $S \rightarrow aSb$. The scanned symbol does not tell us which is the right one. Suppose we now use a look-ahead and consider the first two symbols, finding that they are $aa$. Does this allow us to make the right decision? The answer is still no, since what we have seen could be a prefix of $a$ number of strings, including both $aabb$ or $aabbab$. In the first case, we must start with $S \rightarrow aSb$, while in the second it is necessary to use $S \rightarrow SS$. The grammar is therefore not an $LL (2)$ grammar. In a similar fashion, we can see that no matter how many look-ahead symbols we have, there are always some situations that cannot be resolved.

The above explanation which my mates gives, quite matches with that of Linz, but the difference is that my mates are talking about the language and Linz talks about the grammar.

I came up with a grammar for the language in $\text{GATE-CS-2020}$ paper.

$$S\rightarrow S_1 | S_2$$

$$S_1 \rightarrow aS_1 b | \epsilon$$

$$S_2\rightarrow aS_2| \epsilon$$

which is not $LL(k)$ for any $k$ using similar logic as in Linz text. But proving that a grammar is not $LL(k)$ for any $k$ does not say anything about the language, as Linz says:

This observation about the grammar does not imply that the language is not deterministic or that no LL grammar for it exists.

then Linz removes the problem with the grammar and comes up with a "more not obvious form" (but does not explain how) which is $LL$ and equivalent to the original grammar in example 7.11

$$S_0 \rightarrow aSbS $$ $$S \rightarrow aSbS| \epsilon$$

---

So given such a question about the "language" as in the $\text{GATE-CS-2020}$ paper, how should one proceed? Or what should be the thinking approach?

Answer 1

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language $$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$ is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$.

---

You mention a confusion between grammars and languages. By definition, a language is $\mathrm{LL}(k)$ if it has an $\mathrm{LL}(k)$ grammar. To show that a language is not $\mathrm{LL}(k)$, you have to show that it has no $\mathrm{LL}(k)$ grammar.

Answer 2

I would approach this question in this way, (k) in $\mathrm{LL}(k)$ means the number of lookaheads. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see aaaa then by just looking at the first k symbols, you can't make the decision whether it is aaaa or aaaabbbb.

No matter how large the value of k is, there will always be some string which has the number of a's larger than the lookahead, for which we couldn't decide what string it is.

In short, here $\mathrm{LL}(k)$ cannot conclusively distinguish that whether the string is from $ a^n$ or from $ a^n b^n $.

Another reason that you can give is that the language here is a union of two languages which have common prefix. Hence the $\mathrm{LL}(k)$ cannot parse it using any value of lookahead k.

---

I agree that a language is $\mathrm{LL}(k)$ if there is an $\mathrm{LL}(k)$ grammar which recognizes the language.

But the language can also be $\mathrm{LL}(k)$ and has non-$\mathrm{LL}(k)$ grammars which recognize the language. Hence, If a language is $\mathrm{LL}(k)$, it does not mean that it has $\mathrm{LL}(k)$ grammar.

To understand more clearly why the language here is not LL(k),you can have a read of this LL(k) languages are closed under union with finite languages.