形式陈述

上下文无关文法可化为 Chomsky 范式：除可能的开始规则 $S\to\varepsilon$$S\to \epsilon$ 外，每条产生式为 $A\to BC$$A\to BC$ 或 $A\to a$$A\to a$，其中 $A,B,C$$A,B,C$ 是非终结符、$a$$a$ 是终结符；通常还要求开始符号不出现在任何右部。转换依次处理无用符号、$\varepsilon$$\epsilon$ 产生式、单位产生式与长右部，并为混合在长右部中的终结符引入新非终结符。所得文法与原文法生成相同语言，或仅按约定单独处理 $\varepsilon$$\epsilon$。

直觉

CNF 把任意语法树规范成二叉分叉：内部节点每次产生两个非终结符，叶层再产生单个终结符。结构统一后，解析区间可以按切分点动态规划。

例子与边界

规则 $A\to BCD$$A\to BCD$ 可引入 $X\to CD$$X\to CD$ 后写为 $A\to BX$$A\to BX$；规则 $A\to aB$$A\to aB$ 可引入 $T_a\to a$$T_a\to a$ 后写为 $A\to T_aB$$A\to T_{a}B$。转换一般不保持语法树唯一性，更不保持无歧义性；它只保证语言等价。空语言、只含空字的语言和允许开始符号出现在右部的教材约定需要分别处理，不能机械套用同一规则表。

推论与应用

CNF 是 CYK 算法、CFG 泵引理证明和许多文法复杂性分析的标准预处理，同时把长度 $n$$n$ 的非空词的推导树高度与叶数关系变得可控。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。