乔姆斯基层级——自动机的四个层级
上级：logic
语言学家乔姆斯基（Chomsky，1956）把形式文法分成四个嵌套的类型；每一类型都对应一类自动机（按它拥有多少内存区分）和一类语言。图灵机是最外层的一级。
| 类型 | 文法 | 自动机 | 内存 | 语言 | 例子 |
|---|---|---|---|---|---|
| 3 | 正则 | 有限自动机（DFA/NFA） | 无 | 正则语言 | a*b* |
| 2 | 上下文无关 | 下推自动机（一个栈） | 一个栈 | 上下文无关语言 | aⁿbⁿ、括号配对、绝大多数语法 |
| 1 | 上下文相关 | 线性有界自动机（纸带 ≤ 输入长度） | 有界纸带 | 上下文相关语言 | aⁿbⁿcⁿ |
| 0 | 无限制 | 图灵机 | 无界纸带 | 递归可枚举语言 | 一切可计算的东西 |
严格包含关系：正则 ⊊ 上下文无关 ⊊ 上下文相关 ⊊ 递归可枚举。
这道阶梯的本质是内存
- 无内存 → 有限自动机只能处于有限多个状态之一，它不会计数，所以在
aⁿbⁿ上失败。 - 一个栈 → 能处理嵌套/递归（括号配对），但只能后进先出；在
aⁿbⁿcⁿ上失败（需要同时计两个数）。 - 有界纸带 → 对应上下文相关；仍然可判定（配置数有限）。
- 无界纸带 → 完整的计算能力。图灵机（Type 0）之所以位于最顶层，正是因为无界内存等于通用计算。
不可判定性从哪里冒出来
从Type 1（可判定）跳到Type 0（只是半可判定），正是那次相变：判断一个字符串是否属于某个上下文相关语言是可判定的，但判断它是否属于某个递归可枚举语言只是可识别的——判定它就等价于停机问题（历史）。无界内存一步之间同时买下了通用性和不可判定性。
语言学动机
乔姆斯基真正想说的是自然语言：有限状态（Type 3）文法抓不住从句的嵌套结构，所以语言至少需要上下文无关文法；而交叉依存（cross-serial dependencies）之类的现象又把它推向了温和的上下文相关。这套层级体系诞生的初衷，就是要说明"人类句法不是正则的。"
为什么恰恰是一个语言学家搭建了这套体系，完整的故事见 → history。
每一级（子节点）
- regular-languages — Type 3：有限自动机 = 正则表达式，无内存。
- context-free-languages — Type 2：一个栈，嵌套。
- context-sensitive-languages — Type 1：有界纸带，仍可判定。
- recursively-enumerable-languages — Type 0：图灵机，不可判定性由此开始。