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

A context-free grammar has left recursion if there exists a non-terminal $X$ such that $X \Rightarrow^+ X\alpha$ for some string $\alpha$.

Let us analyze each option:

• Option (A):

  • $A \rightarrow Aa \mid \text{b}$

  This contains immediate (direct) left recursion on $A$ ($A \rightarrow Aa$).

• Option (B):

  • $S \rightarrow Ab \mid Bb \mid \text{c}$

  • $A \rightarrow Bd \mid \varepsilon$

  • $B \rightarrow \text{e}$

  Let us compute the leading non-terminals reachable from each non-terminal:

  • $S \Rightarrow Ab \Rightarrow Bdb \Rightarrow \text{edb}$ or $S \Rightarrow b$

  • $S \Rightarrow Bb \Rightarrow \text{eb}$

  • $S \Rightarrow \text{c}$

  • $A \Rightarrow Bd \Rightarrow \text{ed}$ or $A \Rightarrow \varepsilon$

  • $B \Rightarrow \text{e}$

  No non-terminal $X \in \{S, A, B\}$ can derive a sentential form starting with itself ($X

ot\Rightarrow^+ X\alpha$). Hence, this grammar is free from left recursion.

• Option (C):

  • $S \rightarrow Aa \mid B$

  • $A \rightarrow Bb \mid Sc \mid \varepsilon$

  • $B \rightarrow \text{d}$

  Derivation: $S \Rightarrow Aa \Rightarrow Sca$. Since $S \Rightarrow^+ Sca$, there is indirect left recursion on $S$.

• Option (D):

  • $S \rightarrow Aa \mid Bb \mid \text{c}$

  • $A \rightarrow Bd \mid \varepsilon$

  • $B \rightarrow Ae \mid \varepsilon$

  Derivation: $A \Rightarrow Bd \Rightarrow Aed$. Since $A \Rightarrow^+ Aed$, there is indirect left recursion on $A$ (and similarly on $B$).

Thus, only the grammar in (B) is free from left recursion.