形式陈述

CFL 对并、连接、Kleene 星、反转、同态、逆同态以及与正则语言求交封闭。并、连接和星可直接组合 CFG 或 PDA；与正则语言求交可构造 PDA 与 DFA 的状态乘积。CFL 一般不对交、补或差封闭；若对补封闭，则结合对并封闭和 De Morgan 律会推出对交封闭，与反例矛盾。

直觉

一只栈能在多个语法之间选择、顺序拼接或重复，但同时独立核对两种无界计数通常需要两只栈。有限自动机只增加有限控制，因此和 CFL 求交仍可由一只栈完成。

例子与边界

$L_1=\{a^ib^ic^j\}$$L_1=\{a^i{b}^i{c}^j\}$ 与 $L_2=\{a^ib^jc^j\}$$L_2=\{a^i{b}^j{c}^j\}$ 都是 CFL，但交集为 $\{a^nb^nc^n\}$$\{a^n{b}^n{c}^n\}$，不是 CFL。CFL 与正则语言求交的封闭性常用于泵引理证明中先过滤输入形状。无限并同样不由有限次闭包结论保证。确定性 CFL 有不同的闭包表，不能把一般 CFL 与 DCFL 的结论混用。

推论与应用

这些闭包性质支持文法模块组合、语法过滤以及非上下文无关性的归约证明，也决定哪些语言操作能在解析器生成器中安全实现。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。