Home › GATE CSE › computerscience › Theory of Computation › Chomsky Normal Form (CNF) restricts CFG producti…
Chomsky Normal Form (CNF) restricts CFG production rules to which shapes?
AAny shape — CFGs always allow arbitrary rules
B$A \to BC$ or $A \to a$ (and $S \to \varepsilon$ allowed)
C$A \to a$ only
D$A \to aB$ only (right-linear)
Answer & Solution
Correct answer: B. $A \to BC$ or $A \to a$ (and $S \to \varepsilon$ allowed)
1. CHOMSKY NORMAL FORM (CNF): every production rule has one of these shapes:
- $A \to BC$ (two non-terminals)
- $A \to a$ (one terminal)
- $S \to \varepsilon$ (only allowed for the start symbol)
2. EVERY CFG (that doesn't generate just $\{\varepsilon\}$) can be converted to an equivalent CNF grammar.
3. WHY useful: CNF is the basis for the CYK algorithm — a $O(n^3)$ parsing algorithm. Without CNF, parsing CFGs is more complex.
4. Other restricted forms exist (Greibach Normal Form: $A \to a\alpha$). Option D describes a right-linear grammar (which actually generates REGULAR languages, not CFLs).
5. Options A, C, D mischaracterise CNF.
_Source: Jeff Erickson, "Models of Computation", §5.8 (Chomsky Normal Form)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?