Chomsky 层级

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

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

语言

由 $S\to aSb\mid \epsilon$ 生成，而正则泵引理理路正则语言泵引理Pumping lemma for regular languages足够长的正则语言成员必有一段位于短前缀中的非空环，可删除或重复任意多次而仍留在语言中。证明它非正则，给出 $\mathrm{REG}⊊\mathrm{CFL}$。语言

是上下文有关语言理路上下文有关语言Context-sensitive language · CSL可由非收缩文法生成、允许产生式读取局部上下文的形式语言类。，而上下文无关泵引理理路上下文无关语言泵引理Pumping lemma for context-free languages足够长的上下文无关语言词存在两个可同步泵送的片段。证明它非 CFL，分开 CFL 与 CSL。停机语言理路停机问题不可判定性Halting problem · Undecidability of halting用总停机判断器的自反转构造证明 HALT 不可判定，并区分识别、有限步数检查与局部终止性证明。 $HALT$ 图灵可识别却不可判定；LBA 语言均可判定，因此 $HALT\notin \mathrm{CSL}$，分开 CSL 与 RE。

“Type 1 规则长度不减”有空字例外，若省略开始符号限制，例外可能在推导内部反复收缩。Type 3 的左线性与右线性文法都生成正则语言，但在同一文法中任意混用两类规则可以生成非正则语言。例如 $S\to aA$ 是右线性规则，$A\to Sb\mid b$ 是左线性规则，合在一起却生成 $\{a^n{b}^n:n\ge 1\}$。

给定任意不受限文法，判断它生成的语言是否正则、是否为空，都是不可判定问题。因此这张包含图刻画的是语言类之间的数学关系，并不提供从任意文法自动找出最低层描述的算法。

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

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