Left Recursion and Normal Forms: CNF vs GNF vs BNF

In a keyword grammar, a nonterminal $A$ is left-recursive if there is a derivation $A \Rightarrow^+ A\alpha$ for some string $\alpha$ (i.e., $A$ can derive a sentential form that begins with $A$). This notion matters because many top-down parsers (e.g., naive recursive-descent) can loop when confronted with left recursion.

For context-free grammar “normal forms”:

• keyword A grammar form where productions are restricted to $A\to BC$ or $A\to a$ (with an allowance for special start-symbol rules in some definitions).
• keyword Productions are of the form $A\to a\alpha$ where each rule begins with a terminal.
• keyword A general notation for context-free grammars with production rules like $A ::= \text{expression}$ (typically no restriction that prevents left recursion).

Key intuition:
If every production for a nonterminal starts with a terminal (as in GNF), then it cannot immediately or indirectly “start by expanding itself” at the left edge in the same way left recursion is defined; whereas CNF and especially BNF do not enforce that “leftmost expansion begins with a terminal.”

The multiple-choice question

Which of the following does not have left recursions?

(i) Chomsky normal form
(ii) Greibach normal form
(iii) Backus-Naur form
(iv) All of the above

From standard grammar theory: Greibach normal form is designed so that derivations from nonterminals begin with terminals in a way that avoids left recursion in the usual sense for the nonterminal rewriting process. BNF is general and can represent left-recursive grammars. CNF does not universally eliminate left recursion either, because it permits rules $A\to BC$ where $B$ could derive strings that start with $A$.

Therefore, the correct choice is:

✅ (ii) Greibach normal form

Why GNF avoids left recursion (conceptual proof sketch)

In keyword every production has the shape: $A \to a\alpha$ where $a$ is a terminal and $\alpha$ is (possibly empty) a string of nonterminals.

Consider the leftmost derivation of $A$:

• The first symbol produced at the left edge must be the terminal $a$ (because the first production used from $A$ starts with a terminal).
• To have left recursion $A \Rightarrow^+ A\alpha$, the leftmost symbol of the sentential form after some steps must again begin with $A$.
• But under GNF, after expanding $A$ (at the left edge), the derivation immediately places a terminal at the leftmost position; you cannot “recover” a sentential form whose leftmost symbol is $A$ without violating the property that expansions at the left edge begin with terminals.

So GNF’s “leftmost terminal starts” structure blocks the left-recursive pattern.

CNF and BNF can still be left-recursive

CNF restricts productions to: $A \to BC \quad \text{or} \quad A \to a$ But it does not force that the first step from a nonterminal begins with a terminal—it can begin with another nonterminal $B$. If $B$ can derive a string whose leftmost nonterminal expansion leads back to $A$, you can get left recursion.

BNF imposes no such structural restriction. Since BNF can express arbitrary productions, it can represent grammars that are directly left-recursive, such as: $A \to A\alpha$ which is immediate left recursion by definition.