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

Correct answer: The grammar with productions S → Ab | Bb | c , A → Bd | ε , B → e is free from left recursion.

Definition: A grammar is left-recursive if a nonterminal can derive a string whose leftmost symbol is the same nonterminal (directly or indirectly).

• Grammar S → AB ; A → Aa | b ; B → c :

  A has the production A → A a, which is immediate left recursion (A ⇒ A a). Therefore this grammar is not free from left recursion.

• Grammar S → Ab | Bb | c ; A → Bd | ε ; B → e :

  No nonterminal has a production that begins with itself, and there is no indirect chain that returns the same nonterminal to the leftmost position. B produces a terminal (e), and A produces either B d (which begins with a terminal after expanding B) or ε. Thus no nonterminal X satisfies X ⇒+ X α, so this grammar is free from left recursion.

• Grammar S → Aa | B ; A → Bb | Sc | ε ; B → d :

  S → A a and A → S c give S ⇒ A a ⇒ S c a, so S ⇒+ S α (indirect left recursion). Therefore this grammar is not free from left recursion.

• Grammar S → Aa | Bb | c ; A → Bd | ε ; B → Ae | ε :

  A → B d and B → A e produce A ⇒ B d ⇒ A e d, so A ⇒+ A α (indirect left recursion). Thus this grammar is not free from left recursion.

Conclusion: Only the second grammar listed above (S → Ab | Bb | c ; A → Bd | ε ; B → e) is free from left recursion.