CFL闭包性质

上下文无关语言在以下方面是封闭的：

• 并集
• 连接
• Kleene星号运算

并集

设L₁和L₂为两个上下文无关语言。则L₁ ∪ L₂也是上下文无关的。

示例

设L₁ = { aⁿbⁿ , n > 0}。对应的文法G₁将具有P: S1 → aAb|ab

设L₂ = { c^md^m , m ≥ 0}。对应的文法G₂将具有P: S2 → cBb| ε

L₁和L₂的并集，L = L₁ ∪ L₂ = { aⁿbⁿ } ∪ { c^md^m }

对应的文法G将有额外的产生式S → S1 | S2

连接

如果L₁和L₂是上下文无关语言，则L₁L₂也是上下文无关的。

示例

语言L₁和L₂的并集，L = L₁L₂ = { aⁿbⁿc^md^m }

对应的文法G将有额外的产生式S → S1 S2

Kleene星号

如果L是上下文无关语言，则L*也是上下文无关的。

示例

设L = { aⁿbⁿ , n ≥ 0}。对应的文法G将具有P: S → aAb| ε

Kleene星号L₁ = { aⁿbⁿ }*

对应的文法G₁将有额外的产生式S1 → SS₁ | ε

上下文无关语言在以下方面不是封闭的：

• 交集 - 如果L1和L2是上下文无关语言，则L1 ∩ L2不一定是上下文无关的。

• 与正则语言的交集 - 如果L1是正则语言，L2是上下文无关语言，则L1 ∩ L2是上下文无关语言。

• 补集 - 如果L1是上下文无关语言，则L1’可能不是上下文无关的。