CFL 闭包属性

上下文无关语言在以下情况下封闭 −

• Union
• Concatenation
• Kleene Star 操作

Union

假设 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 Star

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

示例

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

Kleene Star L₁ = { aⁿbⁿ }*

相应的语法 G₁ 将具有附加产生式 S1 → SS₁ | ε

上下文无关语言在 − 下不封闭。

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

• 与常规语言的交集 − 如果 L1 是常规语言，而 L2 是上下文无关语言，则 L1 ∩ L2 是上下文无关语言。

• 补充 − 如果 L1 是上下文无关语言，则 L1' 可能不是上下文无关的。