Chomsky 层级

形式陈述 ​

Chomsky 层级从形式文法公理库形式文法Formal grammar · Generative grammar以终结符、非终结符、产生式和开始符号有限描述语言的通用生成系统。的共同语法出发，按产生式限制把形式语言分成四层：

1. Type 3 正则语言：右线性或左线性文法生成，与有限自动机识别的正则语言公理库正则语言Regular language能被某个有限自动机识别的形式语言。相同。
2. Type 2 上下文无关语言：规则形如 $A\to \gamma$，左侧只有一个非终结符，与上下文无关文法公理库上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。及下推自动机对应。
3. Type 1 上下文有关语言：可由非收缩文法生成，与非确定性线性有界自动机公理库线性有界自动机Linear-bounded automaton · LBA工作带可访问区域被输入长度的常数倍限制的非确定性图灵机。接受的语言相同。空字通常通过受控的 $S\to \epsilon$ 例外处理，并要求 $S$ 不出现在右侧。
4. Type 0 递归可枚举语言：产生式 $\alpha \to \beta$ 只要求 $\alpha$ 含非终结符，与图灵可识别语言公理库可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。相同。

这些语言族满足严格包含

$$\mathrm{REG}⊊\mathrm{CFL}⊊\mathrm{CSL}⊊\mathrm{RE}.$$

包含关系来自模型模拟或放宽产生式限制；严格性则需要分离语言。可判定语言位于 CSL 与 RE 之间，但它不是 Chomsky 四层中额外插入的一个 grammar type。

直觉 ​

产生式能观察的上下文越多、允许改写的形状越自由，文法就能协调越复杂的远距离约束。正则文法只需有限状态；上下文无关文法可递归嵌套；上下文有关文法能在受控空间中同步多个区域；不受限文法则达到一般图灵机的可识别能力。

层级比较的是语言是否存在某种受限描述，而不是手头那份文法写得多复杂。同一个正则语言完全可以由一份 Type 0 文法生成，它仍属于最低所需能力的正则层。

例子与边界 ​

语言

$$L_1=\{a^n{b}^n:n\ge 0\}$$

是上下文无关但非正则，给出 $\mathrm{REG}⊊\mathrm{CFL}$。语言

$$L_2=\{a^n{b}^n{c}^n:n\ge 1\}$$

是上下文有关语言公理库上下文有关语言Context-sensitive language · CSL可由非收缩文法生成、允许产生式读取局部上下文的形式语言类。但非上下文无关，分开 CFL 与 CSL。接受问题 $A_{TM}$ 图灵可识别却不可判定；LBA 语言均可判定，因此 $A_{TM}\notin \mathrm{CSL}$，分开 CSL 与 RE。

“Type 1 规则长度不减”有空字例外，若省略开始符号限制，例外可能在推导内部反复收缩。Type 3 的左线性与右线性文法都生成正则语言，但在同一文法中任意混用两类规则可能越出简单正规形，不能只看每条规则短就判定类型。

层级不声称每个语言都有容易发现的最低层描述。给定任意不受限文法，判断它生成的语言是否正则或是否为空通常不可判定。层级也不按自然语言的“语法复杂程度”分类，而只处理精确定义的字符串集合。

推论与应用 ​

严格包含的证明由两部分组成：较弱机器可由较强机器模拟，给出包含；泵引理、闭包性质或不可判定性提供分离见证。Type 1 的机器刻画需要CSL–LBA 等价定理公理库CSL–LBA 等价定理CSL-LBA equivalence · Kuroda theorem上下文有关语言恰为非确定性线性有界自动机接受的语言。的双向构造，不能仅凭层级图宣布。

层级为词法分析、语法解析、受空间约束的验证和一般程序识别提供模型选择。正则与上下文无关层拥有许多有效判定算法；越向上表达能力越强，通用分析问题也越容易不可判定。资源复杂度还会在同一语言层内部继续细分，因此 Chomsky 层级不能替代时间、空间复杂度分类。

参考资料

• Noam Chomsky, “Three Models for the Description of Language,” IRE Transactions on Information Theory 2(3), 1956, 113–124.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, Chs. 3, 5, and 11.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, Chs. 1–4 and 8.