GATE CS 2017 Set 2 — Question 32

The problem asks for a grammar that is not left recursive and is equivalent to the given grammar G.First, let's analyze the given grammar G:

This grammar has direct left recursion in the productions for E (E -> E - T) and T (T -> T + F). A grammar is left recursive if it has a non-terminal A such that there is a derivation $A \Rightarrow^+ A\alpha$ for some string $\alpha$. Both E and T satisfy this.The question requires a grammar that is not left recursive. Let's check the options:

• Option (A): This is the same as grammar G. It is left recursive. So, (A) is incorrect.
• Option (B): This grammar contains the production T -> T + F. This is a direct left recursion for the non-terminal T. Therefore, this grammar is left recursive. So, (B) is incorrect.
• Option (C): Let's check for left recursion.
• E -> TX: The right side starts with a terminal or a different non-terminal (T).
• X -> -TX: The right side starts with a terminal -.
• T -> FY: The right side starts with a different non-terminal (F).
• Y -> +FY: The right side starts with a terminal +.
• F -> (E) | id: The right side starts with terminals ( or id.

None of the productions are of the form A -> Aα. This grammar is not left recursive.
Now, let's check for equivalence. This grammar is derived from G by applying the standard algorithm for eliminating left recursion.
For E -> E - T | T, we have $A=E, \alpha=-T, \beta=T$. The transformation is $E \rightarrow T E'$, $E' \rightarrow -T E' | \epsilon$. This matches the productions for E and X in option (C) (with X being $E'$).
For T -> T + F | F, we have $A=T, \alpha=+F, \beta=F$. The transformation is $T \rightarrow F T'$, $T' \rightarrow +F T' | \epsilon$. This matches the productions for T and Y in option (C) (with Y being $T'$).
Since this grammar is obtained by the standard left recursion elimination algorithm, it is equivalent to G.
Thus, option (C) is not left recursive and is equivalent to G.

• Option (D): This grammar is not left recursive. However, it is not equivalent to G. For example, in G, T can derive id + id (T -> T+F -> F+F -> id+id). In grammar (D), T can only derive id (T -> id). Therefore, the language generated by (D) is a small subset of the language generated by G. So, (D) is not equivalent.

Based on the analysis, only option (C) satisfies both conditions: it is not left recursive and it is equivalent to G.