Which of the following productions eliminate left recursion in the production given below: S -> Aa | b, A -> Ac | Sd | epsilon
- A. S -> Aa | b, A -> bdA', A' -> A'c | A'ba | A | epsilon
- B. S -> Aa | b, A -> A' | bdA', A' -> cA | adA' | epsilon
- C. S -> Aa | b, A -> A'c | A'd, A' -> bdA' | cA | epsilon
- D. S -> Aa | b, A -> cA' | adA' | bdA', A' -> A | epsilon
Answer: B. S -> Aa | b, A -> A' | bdA', A' -> cA | adA' | epsilon
Explanation: Resolving indirect left recursion. Substitute S in A: A -> Ac | (Aa|b)d | e => A -> Ac | Aad | bd | e. Immediate left recursion on A: A -> Ac | Aad. Beta parts: bd, e. A -> bdA' | A'. A' -> cA' | adA' | e.