Left recursion

Question

In this question should we eliminate left recursion by putting values of S and A in the respective productions so answer will be c but if according to the given production than answer will be a how to solve?

Answer 1

In your question, it's not only have left recursion but also have loop...

in loop cases first you have break the loop, for that change any one variable of them then another variable doesn't lead to loop

1) change A

                 A-> Sca/Ada/b

                 S->Sc/Ad

it looping again and again...... therefore don't change A

2) Change S

           S->Sc/Sad/bd

          A-> Sa/b

it's does not looping but have left recursion.... now eliminate the left recursion..

E-> Eα₁/ Eα₂/.../Eα_n/β₁/β₂/.../β_m 

is changed as

E -> β₁E'/β₂E'/.../β_mE' 

E' -> α₁E'/ α₂E'/.../α_nE' / ∈

According to the formula...

          S -> bdS'

         S' -> cS' / adS' /  ∈

          A-> Sa/b

Comments

Shaik Masthan how to know that in question that which production we need to change.?

---

i tried with A production, it didn't work... Then i tried with S production... Like that we have to check... If both work then it's our choice to change any production

---

Sir please explain one more time...i have a doubt here...

If grammar (from dragon book e.g. )

S-> Aa | b

A->Ac | Sd | €    (€=epsilon)

Then can we eliminate left recursion...?

Because they say in left recursion  algorithm :- input grammar must have  no cycle  or € productions.

They also mentioned " this procedure eliminates all immediate let recursion but it doesn't eliminate left recursion involving derivations of two or more steps."

Please explain this what they says...

Answer 2

In given question indirect recursion is present . So at first convert into direct recursion.