GATE CSE 2016 Set 2 | Question: 45

Question

Which one of the following grammars is free from left recursion?

• A. $S \rightarrow AB$
  $A \rightarrow Aa \mid b$
  $B \rightarrow c$
• B. $S \rightarrow Ab \mid Bb \mid c$
  $A \rightarrow Bd \mid \epsilon$
  $B \rightarrow e$
• C. $S \rightarrow Aa \mid B$
  $A \rightarrow Bb \mid Sc \mid \epsilon$
  $ B \rightarrow d$
• D. $S \rightarrow Aa \mid Bb \mid c$
  $A \rightarrow Bd \mid \epsilon$
  $B \rightarrow Ae \mid \epsilon$

Comments

A context free grammar is said to be left recursive if it has a non-terminal $A$ such that there is a derivation $A ⇒^+ Aα$  for some sequence of grammar symbols $α$. 
For Example:

The following grammar is left-recursive:
$A → Bb ; A → a$
$B →Cc ; B → b$
$C → Aa ; C → c $
 

Answer 1

Option (A) has immediate left recursion."$A \rightarrow Aa$"

Option (C) has indirect left recursion "$S\rightarrow Aa \stackrel{A\rightarrow Sc}{\Longrightarrow} Sca$"

Option (D) has indirect left recursion "$A\rightarrow Bd \stackrel{B\rightarrow Ae}{\Longrightarrow} Aed$"

Option (B) is free from left recursion. No direct left recursion. No indirect left recursion.

Correct Option: B

Comments

Ashish Sir, why (b) is not in left recursion since it is of the form A->Ba/b where a,b∊T*. I think the answer should be (a)

---

@ashish why not be is direct left recursion????I did not get plz clarify

---

Option A cannot be free from left recursion because term A->Aa causes left recursion.

Answer 2

make the dependency graph on basis of variable if there is any no cycle then it is free from left recursion

Comments

please show how would u draw the precedence graph for the same

Answer 3

A has left recursion directly in the second production.

 

For other options, remove the epsilon production from them. In the resulting set of productions try to take each Terminal and see if substituting it directly in other places will lead to left recursion.

 

This ends up happening In options C and D, where Terminal A produces left recursion in terminal S, and Terminal B produces left recursion in terminal  A respectively.

 

Thus B is the answer

Answer 4

Take some sample input, 1 to 2 random language would work, then try making a parse tree either in mind or pen and paper would work. You will get to see that apart from option (B), the rest all are showing left recursion some or the other way. While in option B if we simply substitute single productions into the respective productions, it’s visible that left recursion doesn’t exist. I hope this helps.

Comments

Indirect left recursion means when we go from one production to another production and then that new productions sends back to the last production from which we came. Here the production is of the form:

X → Y a

Y → X b