我们已经认识了两类机器——DFA 只能沿输入带前进，PDA 多了一个可推可弹的栈。既然 PDA 是「带栈的升级版」，那原来 DFA 能做的事，PDA 还能做吗？

上一页梳理了CFL的必要条件，但满足必要条件≠是CFL。要一锤否定一个语言不是CFL，需要泵引理。它为什么能做到？核心藏在语法树的「高度」上。

泵引理把CFL的「能拆能泵」拆成五个变量和一个保证。

树形结构视角：证明存在重复的变量推导

用泵引理证非CFL，分三步完成反证。

把泵长 p 直接设成 n，穷举候选串 aⁿbⁿcⁿ 的合法泵分拆并检查 i=0。

令 n=p 后，三个符号块都达到长度上界；程序穷举 u、v、w、x、y。删去 v、x 后字符计数不可能相等，因此任意正整数 p 都不是泵长度。

关于「任意非上下文无关语言都能用泵引理证明它不是 CFL」这一论断，下列分析正确的是？

泵引理判定『不是 CFL』，是排除法。换个角度：对 CFL 做某个运算，结果仍属于 CFL 吗？这就是闭包性问题，也是正则语言与 CFL 区别最显眼的地方。

看图：从左侧 CFL 输入出发，经五种操作后全部汇入「结果仍为 CFL」——五条路径全封闭。

证明并集封闭的关键一招：让一个新符号同时牵出两套文法。

连接与星闭包都靠构造新文法：把已有产生式稍作改造，就能让新文法产生拼接或迭代后的语言。

交运算与补运算：CFL的边界在哪里

设L1={a^n b^n c^m | n,m≥1}, L2={a^m b^n c^n | n,m≥1}。L1∩L2仍是CFL吗？

闭包自测里我们用过并、连接、星这些 CFL 封闭的运算。还有一类更强的运算——同态：把每个符号替换成一段字符串，结果仍是 CFL。先把定义钉牢。

通过三步构造，把CFL在同态下的像也写成CFL。

上页把 CFL 沿 h 正向送出，得到仍是 CFL 的 h(L)；现在站到输入端，反查哪些原串的像会落进 L。

构造一台PDA，用非确定性逐符号模拟h(x)的展开，让栈操作与原PDA同步。

用 Python 演示 h(a)=01、h(b)=10 对 L={aⁿbⁿ} 的逐字符替换过程。

字典 H 给出同态映射；h 函数逐字符查表拼接；循环把 L 中每个串变成 (01)ⁿ(10)ⁿ，结果仍由 CFG 产生。

前面闭包性把问题变成一个现场：让 PDA 抱着栈经过有限状态门禁，筛选之后，栈结构还在吗？

图分三行读：上行 PDA 带栈、中行 DFA 无栈、下行是两机的乘积。读同一符号时两机同步转移。

前面花了不少篇幅在构造证明——构造 PDA、文法，证明 CFL 满足或不满足某些性质。现在换个角度：给定一个 CFG，能用算法回答它哪些问题？这一页聚焦三大经典判定。

先化简语法,再自底向上填表,看起始符能否推出整个串。

CSL 比 CFL 表达力更强，但更强的是存储与改写能力，并非成员性判定；真正边界出现在空性和有限性。

下列关于上下文无关语言（CFL）判定问题的说法，哪一项正确？

• ✓泵引理是必要条件，不是充分判据
• ✓并、连接、星号及同态、逆同态均保持CFL
• ✓CFL与正则语言交仍为CFL；一般CFL的交不必CFL
• ✓CYK判定成员性；空性也可判定，但等价性等不可判定

课后花十分钟独立思考这三个问题，再对照参考答案——有些结论比直觉更微妙。