1,068 views
For which of the following languages a LL(1) grammar does not exist?
1. $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$
2. $\{ a^n b^m \mid m,n \geq 0 \}$
3. $\{a^ib^j\mid i\geq j\}$
4. $\{a^ib^j\mid i= j\}$

but in the question it's not mentioned whether i>=0 or j>=0 @abhishek
What is the ans? and why?

A language can have many grammars but a grammar can produce only 1 language.

An $LL(1)$ grammar has the following properties

1. It should NOT be ambiguous
2. It should NOT have common prefix problem.(it should be left factored)
3. It should NOT have left recursion.

The $LL(1)$ grammar for the given languages are as follows :-

Option $A.$

$\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$

$S \rightarrow aAb$

$A \rightarrow aAb| \epsilon | o$

Option $B.$

$\{ a^n b^m \mid m,n \geq 0 \}$

$S \rightarrow AB | \epsilon$

$A \rightarrow aA'$

$A' \rightarrow \epsilon | A$

$B \rightarrow bB'$

$A' \rightarrow \epsilon | B$

Option $C.$

$\{a^ib^j\mid i\geq j\}$

$S \rightarrow aS'$

$S' \rightarrow Sb | Ab$           ( Here $FIRST(S) \cap FIRST(A) \neq \phi$ )

$A \rightarrow aA'$

$A' \rightarrow \epsilon | A$

So this is $NOT$ a $LL(1)$ grammar.

Option $D.$

$\{a^ib^j\mid i= j\}$

if $i,j \geq 0$

$S \rightarrow \epsilon |aSb$

if $i,j >0$

$S \rightarrow aS'$

$S' \rightarrow b|Sb$

$\therefore$ For option $C$ we can't generate $LL(1)$ grammar.

by

It should NOT have non-determinism

What does non-determinism mean for a grammar?

Rest part of the answer is fine though why C does not have ant LL(1) grammar can have some reasoning.

non-determinism means that a grammar should not be like $A -> \alpha \beta_1 | \alpha \beta_2$ type of productions...It will get confuse which production to use. This problem is solved using left factoring.

I think we can't directly look at a DCFL language and give a reason that it can't be LL(1) language. We have to write the grammar for the given language and after writing the grammar , we should try to make it non-ambiguous, left factored and non-left recursive.

if we succeed in doing this then the grammar that we get is a LL(1) grammar else if we are not able to follow any one of the constraints then it is not LL(1).

Well, thats not called non-determinism for grammar though the intention is correct.

And like a language can be inherently ambiguous - we can write an ambiguous grammar and try to make ti unambiguous - we can say from the language itself if it is not LL(1). That is why this question was made. Intuitive reasoning you already told as part of the given grammar.