Consider the following expression grammar $G$: $$\begin{aligned} \text{E} &\rightarrow \text{E} - \text{T} \mid \text{T} \\ \text{T} &\rightarrow \text{T} + \text{F} \mid \text{F} \\ \text{F} &\rightarrow (\text{E}) \mid \text{id} \end{aligned}$$ Which of the following grammars is not left recursive, but is equivalent to $G$?

To eliminate immediate left recursion of the standard form:

where $\beta$ does not begin with $A$, we replace the production rules with: $$\begin{aligned} A &\rightarrow \beta A^{\prime} A^{\prime} &\rightarrow \alpha A^{\prime} \mid \epsilon \end{aligned}$$

Applying this transformation to the non-terminals in grammar $G$:

1. For $\text{E} \rightarrow \text{E} - \text{T} \mid \text{T}$: Here, $\alpha = - \text{T}$ and $\beta = \text{T}$. $$\begin{aligned} \text{E} &\rightarrow \text{T}\text{X} \\ \text{X} &\rightarrow -\text{T}\text{X} \mid \epsilon \end{aligned}$$

2. For $\text{T} \rightarrow \text{T} + \text{F} \mid \text{F}$: Here, $\alpha = + \text{F}$ and $\beta = \text{F}$. $$\begin{aligned} \text{T} &\rightarrow \text{F}\text{Y} \\ \text{Y} &\rightarrow +\text{F}\text{Y} \mid \epsilon \end{aligned}$$

3. The non-terminal $\text{F} \rightarrow (\text{E}) \mid \text{id}$ is not left-recursive and remains unchanged.

Combining these yields the grammar in option (C): $$\begin{aligned} \text{E} &\rightarrow \text{TX} \\ \text{X} &\rightarrow -\text{TX} \mid \epsilon \\ \text{T} &\rightarrow \text{FY} \\ \text{Y} &\rightarrow +\text{FY} \mid \epsilon \\ \text{F} &\rightarrow (\text{E}) \mid \text{id} \end{aligned}$$

Distractor analysis:

• (A) retains the original left-recursive rules for $\text{E}$ and $\text{T}$.

• (B) eliminates left recursion only from $\text{E}$, but $\text{T} \rightarrow \text{T} + \text{F}$ remains left-recursive.

• (D) changes the language of the grammar entirely.

Thus, the correct option is (C).