GATE CS 2008 Q50 — Parsing (LL, LR)

To determine which statements are true, let us analyze each one individually:

• Statement I: Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa. (True)
  Left-recursion can always be eliminated from a context-free grammar to produce an equivalent grammar with right-recursion (and vice-versa) using standard algorithms, without changing the language generated by the grammar.


• Statement II: All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations. (False)
  If the language $L(G)$ contains the empty string $\epsilon$, we cannot completely eliminate all $\epsilon$-productions. At least one production of the form $S \rightarrow \epsilon$ (where $S$ is the start symbol) must remain to generate the empty string.


• Statement III: The language generated by a context-free grammar all of whose productions are of the form $X \rightarrow w$ or $X \rightarrow wY$ is always regular. (True)
  A grammar with productions restricted to the forms $X \rightarrow w$ or $X \rightarrow wY$ (where $w \in \Sigma^*$ and $Y$ is a non-terminal) is a right-linear grammar. Right-linear grammars generate exactly the class of regular languages.


• Statement IV: The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees. (True)
  In Chomsky Normal Form (CNF), all production rules are of the form $A \rightarrow BC$ or $A \rightarrow a$ (and possibly $S \rightarrow \epsilon$). Consequently, every internal node in the derivation tree has either exactly $2$ children (for $A \rightarrow BC$) or $1$ child (for $A \rightarrow a$). Since no node has more than $2$ children, the derivation tree is always a binary tree.

Thus, statements I, III, and IV are true.