Chomsky 范式

CNF 把任意上下文无关推导规整为两种动作：一个非终结符分成两个子结构，或直接产生一个终结符。将产生终结符的单边收缩后，长度为 $n$ 的非空字的推导树理路语法树Parse tree · Derivation tree用有序树记录产生式层次，以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。便成为有 $n$ 片叶子的严格二叉树，内部结构可按输入区间动态规划。统一的规则形状方便计数与归纳，代价是增加一些辅助非终结符。

考虑文法 $S\to AB$、$A\to aA\mid \epsilon$、$B\to b$，其语言是 $a^{\ast }b$。先加新开始规则 $S_0\to S$。只有 $A$ 可推出空字，因此删除 $A\to \epsilon$ 时，要在每个出现 $A$ 的右部补上省略它的选择：$S\to AB\mid B$、$A\to aA\mid a$、$B\to b$，并保留 $S_0\to S$。

接着消除单位规则。$S$ 可沿单位规则到达 $B$，$S_0$ 可到达 $S,B$，所以把这些目标的非单位规则复制过来，得到 $S_0\to AB\mid b$、$S\to AB\mid b$、$A\to aA\mid a$、$B\to b$。此时 $S$ 从新开始符号不可达，可以删除。最后引入 $T_a\to a$，把混合右部 $aA$ 改为 $T_{a}A$，结果为

现在每条规则都符合 CNF：直接用 $S_0\to b$ 保留零个 $a$ 的情形，其余推导先产生一个或多个 $a$，再接一个 $b$。若还有长右部 $A\to BCD$，可另引入 $X$，改为 $A\to BX$、$X\to CD$；这一步只二叉化，不承担前面的空字或单位规则消除。

空字由 $S_0\to \epsilon$ 单独保留，因为普通的二叉分裂和终结符规则只会生成非空字。只含空字的语言可保留这一条规则；空语言则可用没有产生式的开始符号表示。新开始符号也把原开始符号出现在右侧的情况隔离开来。

CNF 文法并不唯一，转换也可能显著增大表示。它保证生成语言不变，语法树形状则会随着辅助非终结符改变；消除歧义需要另外分析，不能由范式转换直接得到。

CNF 是 CYK 算法理路CYK 算法Cocke–Younger–Kasami algorithm用区间动态规划判定给定字是否属于 Chomsky 范式文法生成的语言。的输入形式，使“非终结符 $A$ 能否生成区间 $w[i:j]$”可由两段划分递推。上下文无关泵引理也利用二叉语法树高度与重复非终结符。

它从CFG理路上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。通向算法化成员判定和复杂度分析；语法树理路语法树Parse tree · Derivation tree用有序树记录产生式层次，以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。在范式下具有统一形状，便于计数与归纳证明。