(b) As it is the case of indirect recursion so let first make it a direct recursion then apply rules of removal of left recursion.
to make it a direct recursion first production remains unchanged while in second production substitutes the right-hand side of the first production wherever it comes. In the question $S$ comes in the middle of $A$ so substitute the right-hand side of production $S$.Now after substituting it looks like this:
- $A \rightarrow Ac\mid Aad \mid bd \mid \epsilon$
Now remove direct recursion from it
For removal of direct recursion rule:
- $A \rightarrow A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m$
Replace these with two sets of productions, one set for $A:$
- $A \rightarrow \beta_1A^\prime \mid \ldots \mid \beta_mA^\prime$
and another set for the fresh nonterminal $A^{\prime}$
- $A^\prime \rightarrow \alpha_1A^\prime \mid \ldots \mid \alpha_nA^\prime \mid \epsilon$
After applying these rules we'll get:
- $A \rightarrow bdA'\mid A'$
- $A' \rightarrow cA'\mid adA' \mid \epsilon$
Now complete production without left recursion is:
- $S \rightarrow Aa \mid b$
- $A \rightarrow bdA'\mid A'$
- $A' \rightarrow cA'\mid adA' \mid \epsilon$
