The Gateway to Computer Science Excellence
+2 votes
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\}$
in Compiler Design by Veteran (432k points) | 320 views
if answer is C

S- >aSb/A

A-> aA/epsilon

so it has a conflict first of S

?? may be
option a. since DCFL are not closed under union

all the rest options are DCFL.

@Satbir Are you saying option A is not DCFL?

yes sir. In the union after a^n then non determinism can arise for selecting o or b
How can non-determinism happen when b and o are different symbols?
DCFL are not closed under union.

@Uqxkqc Can you please provide the grammar for Option A?

I got like :

$S \rightarrow A/B$

$A \rightarrow aAb/ab$

$B \rightarrow aBb/aob$

Is this right?

yes i think so

but have you got the answer of the question?
If its so then aren't the First sets of A not disjoint? "a" is common in them. They how can it be LL(1)..?
may be you have to do left factoring.
if you know the solution, please tell me so

i will be grateful

In exam,  it is very tough to write grammars for all the languages and then check ambiguity and then remove left recursion and non-determinism and find first and follow in just 3 minutes.. Can anyone please tell, Is there any shortcut to test LL(1) by just seeing the languages?
why D is not the answer? the grammar for such language is S->aSb | ab
here FIRST(aSb) and FIRST(ab) are not disjoint sets hence they'll be placed in the same cell of LL(1) parsing table. So this grammar is not in LL(1)
aditi ,
if we take
S--->aSb /null
Then it is LL(1)
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.

1 Answer

+1 vote
Best answer

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 Boss (24.2k points)
selected by

@Arjun Sir, please check the answer.


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.


I updated my answer.

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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,394 answers
105,445 users