The equivalent production rules corresponding to the production rules S → Sα₁…
2013
The equivalent production rules corresponding to the production rules
S → Sα₁ | Sα₂ | β₁ | β₂ is
- A.
S → β₁ | β₂
A → α₁A | α₂A | λ - B.
S → β₁ | β₂ | β₁A | β₂A
A → α₁A | α₂A - C.
S → β₁ | β₂
A → α₁A | α₂A - D.
S → β₁ | β₂ | β₁A | β₂A
A → α₁A | α₂A | λ
Attempted by 20 students.
Show answer & explanation
Correct answer: D
The grammar exhibits direct left recursion where S appears on the left side of α₁ and α₂.
To eliminate this, introduce a new non-terminal A. The base cases β₁ and β₂ become the start of S's rules.
The recursive parts α₁ and α₂ become the start of A's rules, including a lambda production for termination.
Final rules: S → β₁A | β₂A and A → α₁A | α₂A | λ.
A video solution is available for this question — log in and enroll to watch it.