CFL 封闭特性
上下文无关语言关闭于 -
- 联盟
- 级联
- 克林星行动
联盟
令L 1和L 2为两种上下文无关语言。那么 L 1 ∪ L 2也是上下文无关的。
例子
令 L 1 = { a n b n , n > 0}。对应的语法G 1将有P: S1 → aAb|ab
令 L 2 = { cm d m , m ≥ 0}。对应的文法G 2将有P: S2 → cBb| ε
L 1和 L 2的并集，L = L 1 ∪ L 2 = { a n b n } ∪ { c m d m }
相应的语法G将具有附加产生式S → S1 | S2
级联
如果 L 1和 L 2是上下文无关语言，则 L 1 L 2也是上下文无关语言。
例子
语言 L 1和 L 2的并集，L = L 1 L 2 = { a n b n c m d m }
对应的语法G会有附加产生式S → S1 S2
克林星
如果 L 是上下文无关语言，那么 L* 也是上下文无关的。
例子
令 L = { a n b n , n ≥ 0}。对应的语法G就有P: S → aAb| ε
克林星 L 1 = { a n b n }*
相应的语法 G 1将有附加产生式 S1 → SS 1 | ε
上下文无关语言不封闭-
交集- 如果 L1 和 L2 是上下文无关语言，则 L1 ∩ L2 不一定是上下文无关的。
与正则语言的交集- 如果 L1 是正则语言并且 L2 是上下文无关语言，则 L1 ∩ L2 是上下文无关语言。
补语- 如果 L1 是上下文无关语言，则 L1' 可能不是上下文无关的。