上下文无关语言闭包性质

闭包问题问的是：把两个语言经过某种运算组合后，是否仍能由同一类机器描述。对上下文无关语言，答案呈现鲜明的不对称：一只栈能在多个语法之间选择、顺序拼接或重复，所以并、连接与 Kleene 星号可以通过局部拼接文法实现；交和补却通常需要同时协调两套无界栈式依赖，超出单栈的全局同步能力。有限自动机只增加有限控制，因此 CFL 与正则语言求交仍可由一只栈完成。理解这种能力差异，比单纯背诵闭包表更重要。

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

若 $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\}$，仍是上下文无关语言。

交不封闭还推出补不封闭：若上下文无关语言对补封闭，那么利用其对并封闭和 De Morgan 律，就会得到对交封闭，与上述反例矛盾。这里的论证针对一般上下文无关语言；确定性上下文无关语言具有不同的补封闭性质。

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