Step 1: Order the nonterminals
Let’s fix the order:
S (A₁), A (A₂)
Step 2: i = 1 → Nonterminal S
S → A a | b
Step 3: i = 2 → Nonterminal A
Original:
A → A c | S d | ε
There is immediate left recursion (A → A c)
Also indirect recursion through S → A a, and A → S d
Let’s substitute S into A → S d.
Step 3.1: Substitute S → A a | b into A → S d
From: A → S d
We substitute: S → A a | b
So: A → A a d | b d
Now A becomes: A → A c | A a d | b d | ε
Group them into:
- Left-recursive:
A → A c,A → A a d - Non-left-recursive:
A → b d,A → ε
Step 4: Eliminate Immediate Left Recursion
Let’s use the transformation:
If: A → A α₁ | A α₂ | … | β₁ | β₂ | …
We rewrite as:
A → β₁ A’ | β₂ A’ …
A’ → α₁ A’ | α₂ A’ … | ε
Apply it to our case:
Left-recursive α’s:
α₁ = c
α₂ = a d
Non-left-recursive β’s:
β₁ = b d
β₂ = ε
Final Transformed Grammar
S → A a | b
A → b d A’ | ε A’
A’ → c A’ | a d A’ | ε
Simplification
Since: A → ε A’ ≡ A → A’
We can simplify:
A → b d A’ | A’
A’ → c A’ | a d A’ | ε
Or leave A → ε A' as it is if you’re directly following the algorithm step by step for exam clarity.
Final Grammar without Left Recursion
S → A a | b
A → b d A’ | ε A’
A’ → c A’ | a d A’ | ε