第2型——上下文无关语言（一个栈）
给有限自动机加上一个栈，就得到下推自动机（pushdown automaton）。栈提供了嵌套／递归能力（后进先出）。
下推自动机如何识别 aⁿbⁿ：每读到一个 a 就压入一个标记，每读到一个 b 就弹出一个，最终当且仅当栈为空时接受——栈实际上就是在计数 a 的个数，以便与 b 匹配。
- 文法： 上下文无关——产生式
A → γ（左边只有一个非终结符）。 - 自动机： 下推自动机（PDA）。范式：乔姆斯基范式（Chomsky）／格雷巴赫范式（Greibach）。解析：CYK 算法，
O(n³)。 - 例子：
aⁿbⁿ；平衡括号（Dyck 语言，含多种括号类型）；回文w wᴿ；{ aⁱbʲ : i ≠ j }；匹配的 XML/HTML 标签；带优先级的算术表达式；以及绝大多数编程语言的语法——这正是文法与解析器采用上下文无关的原因。
文法 → 推导 → 语法树
上下文无关文法（CFG）从起始符号开始，通过反复改写来生成字符串。取 S → a S b | a b（它生成 aⁿbⁿ）。推导 aabb：
S ⇒ a S b ⇒ a (a b) b = aabb
语法树记录了这次推导（从左到右读叶子节点，正好拼出该字符串）：
对真实语法而言，语法树还编码了优先级——E → E+T | T、T → T*F | F、F → (E) | id 解析 id + id * id 时，会让 * 处在 + 的下方（结合得更紧）。这种结构性的嵌套，正是 PDA 的"一个栈"被可视化之后的样子，也是 有限自动机 做不到的事。
封闭性： 对并、连接、星号封闭——但对交集和补集不封闭（aⁿbⁿcⁿ = aⁿbⁿc* ∩ a*bⁿcⁿ 是经典的反例）。
泵引理（上下文无关版）足够长的字符串可以拆成
w = uvxyz，其中v,y可以一起泵：对任意i，uvⁱxyⁱz都仍在语言中。
推论：aⁿbⁿcⁿ 不是上下文无关的——一个栈只能追踪一个嵌套计数，而不是两个独立的计数 → 需要升级到 一条有界的纸带。
可判定性： 成员关系是可判定的（即解析）；但两个 CFG 是否等价是不可判定的——这是（远低于图灵能力时）出现的第一道裂缝。
一个栈 vs 两个栈——跳跃是突然的
一个栈 = 上下文无关。两个栈 = 一台完整的图灵机（第0型）：两个栈可以模拟一条纸带——一个保存读写头左边的全部内容，另一个保存读写头及其右边的全部内容；移动读写头就是从一个栈弹出、压入另一个栈。所以从第2型跳到顶层，可能只需要多加一个栈——不需要经过第1型的渐进台阶。（对队列自动机、或双计数器的 Minsky 机来说，是同样的跳跃。）增加内存结构是跨层跳跃，不是逐级爬升。