Chomsky 范式 | Codeboy's Blog

形式陈述

上下文无关文法处于 Chomsky 范式（CNF），若每条产生式形如

A\to BC \qquad\text{或}\qquad A\to a,

其中 $A,B,C$ 是非终结符、 $a$ 是终结符。若语言包含空字，可额外允许新开始符号 $S_0\to\varepsilon$ ，并要求 $S_0$ 不出现在任何产生式右侧。

每个 CFG 都可有效转换为生成同一语言（按上述空字约定）的 CNF 文法。转换通常依次引入新开始符号、消除 ε 产生式与单位产生式、删除无用符号、把长右侧二叉化并把混合右侧中的终结符替换为专用非终结符。

直觉

CNF 把任意上下文无关推导规整为两种动作：一个非终结符分成两个子结构，或直接产生一个终结符。于是长度为 $n$ 的非空字对应一棵严格二叉树，内部结构可按输入区间动态规划。范式的目的不是让文法更易读，而是消除算法分析中无关的规则形状差异。转换会增加辅助非终结符，也不会自动让歧义消失。

例子与边界

规则 $A\to BCD$ 可引入新符号 $X$ 改为 $A\to BX$ 、 $X\to CD$ 。规则 $A\to aB$ 可先设 $T_a\to a$ ，再写 $A\to T_aB$ 。这样每个内部节点恰有两个非终结符孩子，叶层再产生终结符。

边界是空字：普通 $A\to BC$ 、 $A\to a$ 规则无法产生长度零字，因此必须单独处理 $S_0\to\varepsilon$ 。CNF 文法不唯一，转换也可能显著增大文法；若原文法歧义，所得范式通常仍可能歧义。

空语言、只含空字的语言，以及允许原开始符号出现在产生式右部的教材约定都要分别处理；不能把同一张消元规则表机械套在这些退化情形上。转换承诺的是生成语言相同，不是语法树结构或歧义性保持不变。

推论与应用

CNF 是 CYK 算法的输入形式，使“非终结符 $A$ 能否生成区间 $w[i:j]$ ”可由两段划分递推。上下文无关泵引理也利用二叉语法树高度与重复非终结符。

它从CFG通向算法化成员判定和复杂度分析；语法树在范式下具有统一形状，便于计数与归纳证明。

参考资料

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。