Answer

Correct Option: (i) Chomsky Normal Form and (ii) Greibach Normal Form — both have no left recursion; if single choice required, (i) CNF is the textbook answer, and BNF may contain left recursion.

Explanation

Left recursion: Production $A \rightarrow A\alpha$.

• Chomsky Normal Form (CNF): $A \rightarrow BC$ or $A \rightarrow a$, where $B,C\in V$, $a\in T$. No $A$ on RHS leftmost as non-terminal with same $A$, and no $A\rightarrow A\alpha$. No left recursion.
• Greibach Normal Form (GNF): $A \rightarrow a\alpha$, where $a\in T$, $\alpha\in V^*$. Starts with terminal → no left recursion by definition.
• Backus-Naur Form (BNF): General notation for CFG, e.g., $A ::= A + B \mid B$. May contain left recursion (common in expression grammars).

Options:

• (i) CNF → no left recursion ✓
• (ii) GNF → no left recursion ✓
• (iii) BNF → can have left recursion ✗
• (iv) All of above → false because BNF can have it.

If exam expects single answer, CNF (and GNF) are correct; many keys mark (i) Chomsky Normal Form.

Final Answer

CNF / GNF have no left recursion → Option (i) (and (ii)). BNF can have left recursion.