Home » Theory of Computation » Theory of computation miscellaneous » Question

Which one of the following grammars is free from left recursion?

1. S → AB
  A → Aa | b
  B → c
2. S → Ab | Bb | c
  A → Bd | ε
  B → e
3. S → Aa | B
  A → Bb | Sc | ε
  B → d
4. S → Aa | Bb | c
  A → Bd | ε
  B → Ae | ε

Correct Option: B

Grammar A has direct left recursion because of the production rule : A → Aa. Grammar C has indirect left recursion because of the production rules : S → Aa and A → Sc Grammar D has indirect left recursion because of production rules : A → Bd and B → Ae Grammar B doesn't have any left recursion (neither direct nor indirect).