2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ A language is $LL(k)$ if it has an $LL(k)$ grammar. $\endgroup$ – Yuval Filmus Apr 20 at 20:02
  • $\begingroup$ @Yuval Yes this is what Linz also says. But the example he talks about, he comes up with a non obvious transformation and proves that the problem was with the grammar and not with the language. Now trying to prove the LL(k) nature of an unknown language is not an easy task I guess, (from the non obvious transformations that Linz does in the example). But is there any easy way out for such problems in general, I mean the thinking approach. Well in CFG, we can at times argue whether or not the language is inherently ambiguous or not like in $L = \{a^nb^nc^m\} \cup \{ a^n b^m c^m\}$ $\endgroup$ – Abhishek Ghosh Apr 20 at 20:37
  • $\begingroup$ Please help me out in understanding it.. $\endgroup$ – Abhishek Ghosh Apr 20 at 20:42
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the paper information. It is quite a thorough and formal proof. But is there any other intuitive way of satisying one's self that whether a language is $LL(k)$ or not? Or is it the only possibly easy way of proving? Because I feel understanding a proof is eased if one learns the intuition behind it. [ I am a newbie in this field, so do not know much about these things. ] (Or reverse engineering the proof shall give the intuition? Works most of the time... ) $\endgroup$ – Abhishek Ghosh Apr 21 at 9:17
  • 1
    $\begingroup$ After you understand the proof and why it works, you should be able to develop such intuition. $\endgroup$ – Yuval Filmus Apr 21 at 12:14
3
+25
$\begingroup$

DPDAI 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.

$\endgroup$
3
  • $\begingroup$ there are few things that I do not understand in your answer.(1)Did you draw the PDA for the language of the question,or you tried to explain by taking some other example? [The PDA actually accepts $\{a^n\}\cup \{a^nb^{n+1}\}$] (Correct PDA : drive.google.com/file/d/1nvW1cIte7cUs-EDq9jMFWur2FJLiGhKd/… ). (2) you say The grammar of L here possess non-determinism but there is no explicit grammar given in the actual question. (3) Hence, If a language is LL(k), it does not mean that it has LL(k) grammar.:It is guess completely against the definition of $LL(k)$ language. $\endgroup$ – Abhishek Ghosh Apr 28 at 21:59
  • $\begingroup$ 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. : I do not get how is that theorem is to answer the current question as neither $\{a^n\}$ nor $\{a^nb^n\}$ are finite languages. $\endgroup$ – Abhishek Ghosh Apr 28 at 22:10
  • $\begingroup$ Another reason that you can give is that the language here is a union of two languages which have common prefix. Hence the LL(k) cannot parse it using any value of lookahead k. : Could you please elaborate on this point ? $\endgroup$ – Abhishek Ghosh Apr 29 at 6:19

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.