GATE Overflow | Compiler Design | Test 1 | Parsing | Question: 9

Question

For which of the following languages a LL(1) grammar does not exist?

• A. $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n  b^{n} \mid n \geq 1 \}$
  
• B. $\{ a^n b^m \mid m,n \geq 0 \}$
  
• C. $\{a^ib^j\mid i\geq j\}$
  
• D. $\{a^ib^j\mid i= j\}$

Comments

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.

---

You can see Point 4 here

https://gateoverflow.in/299897/common-careless-mistakes

---

@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

---

A->aA1

A1->Ab/ob/b

---

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?

---

@aditi19

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

Answer 1

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.

Comments

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