Which of the following productions eliminate left recursion in the productions…
2013
Which of the following productions eliminate left recursion in the productions given below: S → Aa | b A → Ac | Sd | ε
- A.
S → Aa | b A → bdA' A' → A'c | A'ba | A | ε
- B.
S → Aa | b A → A' | bdA', A' → cA' | adA' | ε
- C.
S → Aa | b A → A'c | A'd A' → bdA' | cA | ε
- D.
S → Aa | b A → cA' | adA' | bdA' A' → A | ε
Attempted by 55 students.
Show answer & explanation
Correct answer: B
The grammar S → Aa | b and A → Ac | Sd | ε contains indirect left recursion. Substituting S into A yields A → Ac | Aad | bd | ε. Eliminating direct left recursion for A results in A → (bd|ε)A' and A' → (c|ad)A'|ε. S remains unchanged.