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

Method: By option elimination

Option 1:

S → AB

A → Aa | b

B → c

Here, there is a left recursion in “A → Aa”

Option 3:

S → Aa | B

A → Bb | Sc | ϵ

B → d

Since, S → Aa and A → Sc which will result in S → Sca

So, it results in a left recursion.

Option 4:

S → Aa | Bb | c

A → Bd | ϵ

B → Ae | ϵ

Since A → Bd and B → Ae

which results in left recursion, A → Aed or B → Bde

Option 2:

S → Ab | Bb | c

A → Bd | ϵ

B → e

This grammar doesn’t include direct left recursive statement or indirect left recursive statement production.