Question 55

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

Analyze Option A:
$S \to AB$
$A \to Aa \mid b$
$B \to c$
The production $A \to Aa$ contains immediate (direct) left recursion. Hence, grammar A is not free from left recursion.

Analyze Option B:
$S \to Ab \mid Bb \mid c$
$A \to Bd \mid \varepsilon$
$B \to e$
Let us check the leading derivations for each non-terminal:

• From $B$: only $B \to e$, which starts with a terminal.
• From $A$: $A \to Bd \implies ed$, or $A \to \varepsilon$.
• From $S$: $S \to Ab \implies Bdb \implies edb$, or $S \to Ab \implies b$ (via $A \to \varepsilon$), or $S \to Bb \implies eb$, or $S \to c$.
  None of the derivations from $S, A,$ or $B$ can produce a sentential form starting with the same non-terminal. Hence, grammar B is free from both direct and indirect left recursion.

Analyze Option C:
$S \to Aa \mid B$
$A \to Bb \mid Sc \mid \varepsilon$
$B \to d$
Here $S \to Aa \implies Sca$, which gives $S \Rightarrow^+ Sca$. This is an indirect left recursion. Hence, grammar C is not free from left recursion.

Analyze Option D:
$S \to Aa \mid Bb \mid c$
$A \to Bd \mid \varepsilon$
$B \to Ae \mid \varepsilon$
Here $A \to Bd \implies Aed$, which gives $A \Rightarrow^+ Aed$. This is an indirect left recursion between $A$ and $B$. Hence, grammar D is not free from left recursion.

Therefore, only grammar B is free from left recursion.