How to Eliminate Indirect Left recursion from this grammar?

Question

$\textbf{Eliminating indirect left-recursion}$

Indirect left-recursion

$S\rightarrow Aa|b$

$A\rightarrow Ac| Sd |\in$

Comments

I have a boubt, S->Aa which gives S->Sd, so sholdn't we apply the ruples to S also??? and if we apply to S then do we have to apply it on A->Sd which gives A->Aad???

---

The Grammer contains indirect left recursion as well as direct left recursion 

Ist remove indirect left recursion hence 2nd production becomes

A->Ac|Aad|bd|epsilon

now remove left recursion from this production

A->bdA^'|epsilonA^' ==>  A->bdA^'|A^' 

A^'->cA^'|adA^'| epsilon

Hence Grammer is 

S->Aa|b

A->bdA^'|A^' 

A^'->cA^'|adA^'| epsilon

Hence option A is correct.

Answer 1

First find the paths where indirect recursion happens. Here indirect recursion A→Sd happening in this production.

Then put all the production of S in that variable.You get $\large A\rightarrow Ac| Aad | bd |\epsilon$

Then do the normal procedure as we remove direct left  recursion.

$S\rightarrow Aa|b$

$A\rightarrow bdA' | A'$

$A'\rightarrow cA' | adA' | \epsilon$

Comments

@MaonjK why are we not applying the same on S??? Is it required yo be performed on both?? or if we aplly on S and not on A, will it be correct???

---

See If we consider $\large S\rightarrow Aa|b$.

So here no indirect left recursion.Because there is no production before $\large S\rightarrow Aa|b$ production.

If you are confused then try to follow this algo while removing left recusion as well as indirect left recusion.

Arrange the production in any order A1,A2,A3,....An.

for(i=1 to n)
for(j=1 to i-1){

 replace each rule of the form $\large A_{i}\rightarrow A_{j}\beta$ by

$\large A_{i}\rightarrow \alpha _{1}\beta |\alpha _{2}\beta |....|\alpha _{k}\beta$

where $\large A_{j}\rightarrow \alpha _{1} |\alpha _{2} |....|\alpha _{k}$ are all current production of $\large A_{j}$ production

}

eleminate immeadiate left recursion among $\large A_{i}$ production.

---

Excellent explaination.

Answer 2

S⟶Aa | b

S⟶Sda | Aca | a | b

Removing left recursion

S⟶ bS' | aS' | AcaS'

S'⟶ daS' |∊

 

A⟶Ac | Sd | ∊

A⟶Ac | Aad | bd | ∈

A⟶bdA'

A'⟶ cA' | adA' |∊

Comments

Could u please explain the procedure? Basically I do not have any idea about eliminating indirect left recursion but i know the direct left recursion method.