上下文无关语言闭包性质

闭包问题问的是：把两个语言经过某种运算组合后，是否仍能由同一类机器描述。对上下文无关语言，答案呈现鲜明的不对称：一只栈能在多个语法之间选择、顺序拼接或重复，所以并、连接与 Kleene 星号可以通过局部拼接文法实现；交可能要求同一输入同时满足两套栈约束，而一只栈未必能同时保留两套信息。补的困难则在于非确定接受是“存在成功分支”：把每条分支的成功与失败互换，不会把存在量词变成“所有分支失败”。有限自动机只增加有限控制，因此 CFL 与正则语言求交仍可由一只栈完成。理解这种能力差异，比单纯背诵闭包表更重要。

令 $L_1=\{a^i{b}^i{c}^j:i,j\ge 0\}$、$L_2=\{a^i{b}^j{c}^j:i,j\ge 0\}$。前者可用 $S_1\to AC$、$A\to aAb\mid \epsilon$、$C\to cC\mid \epsilon$ 生成；后者可用 $S_2\to DB$、$D\to aD\mid \epsilon$、$B\to bBc\mid \epsilon$ 生成。两者分别只要求一对计数相等，故都是 CFL。交集同时要求 $\mathrm{\#}a=\mathrm{\#}b$ 与 $\mathrm{\#}b=\mathrm{\#}c$，于是等于 $\{a^n{b}^n{c}^n:n\ge 0\}$；上下文无关泵引理理路上下文无关语言泵引理Pumping lemma for context-free languages足够长的上下文无关语言词存在两个可同步泵送的片段。证明它不是 CFL。

若 $L_1=\{a^i{b}^i:i\ge 0\}$、$L_2=\{c^j:j\ge 0\}$，则 $L_1{L}_2=\{a^i{b}^i{c}^j\}$ 仍是上下文无关语言：文法先生成匹配的 $a,b$，再生成任意个 $c$。上下文无关语言也对与正则语言的交封闭；例如 $\{a^i{b}^i{c}^j:i,j\ge 0\}$ 与正则语言 $a^{\ast }{b}^{\ast }cc$ 相交后得到 $\{a^i{b}^i{c}^2:i\ge 0\}$，仍是上下文无关语言。

有限并的构造也能直接写出：先把两套文法的非终结符重命名为互不相交，再用新的开始符号增加 $S\to S_1\mid S_2$；连接改用 $S\to S_1{S}_2$，单个语言的星则用 $S\to S_{1}S\mid \epsilon$。重命名防止本来无关的规则意外共用变量。与正则语言求交时，PDA 的状态再记录 DFA 的当前状态：消费字符时两者一起更新，PDA 走 $\epsilon$ 边时 DFA 保持不动，最后要求两者都接受。栈仍只有一条；再由CFG–PDA 等价定理理路CFG–PDA 等价定理CFG–PDA equivalence上下文无关文法与非确定性下推自动机刻画同一语言类；三元变量描述受保护的弹栈段，完整八变量例子及双向归纳将运行转换为推导。把这台乘积机器转换回文法，即得所要求的 CFL 闭包。

交不封闭还推出补不封闭：若上下文无关语言对补封闭，那么利用其对并封闭和 De Morgan 律，就会得到对交封闭，与上述反例矛盾。差也不封闭，否则取 ${\mathrm{\Sigma }}^{\ast }\setminus L$ 就会得到补封闭。这里的论证针对一般上下文无关语言；确定性上下文无关语言具有不同的补封闭性质。无限并也不能由有限并推广：任何语言都是其单字语言的并，而每个单字语言甚至都是正则的。

这些闭包性质让 语言运算理路语言运算Language operations通过集合组合、字的连接、有限重复与编码映射，从已有语言构造新语言。 成为构造新 上下文无关文法理路上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。 的模块化工具，决定哪些组合与语法过滤能在解析器生成器中安全实现，也能服务于非上下文无关性的归约证明：先假设目标语言属于该类，再与精心选择的正则语言相交，把问题化到已知反例。与 正则语言闭包性质理路正则语言闭包性质Closure properties of regular languages正则语言经有限布尔组合、连接、星、反转以及同态像和逆像后仍是正则语言。 对照，还能看出有限状态模型和栈模型在布尔运算上的本质差别。