Automata Theory 简明教程

CFL Closure Property

无上下文语言在 − 下为 closed

  1. Union

  2. Concatenation

  3. Kleene Star operation

Union

设 L1 和 L2 为两种无上下文语言。则 L1 ∪ L2 也是无上下文的。

Example

设 L1 = { anbn , n > 0}。相应的语法 G1 具有 P: S1 → aAb|ab

设 L2 = { cmdm , m ≥ 0}。相应的语法 G2 具有 P: S2 → cBb| ε

L1 和 L2 的并集，L = L1 ∪ L2 = { anbn } ∪ { cmdm }

相应的语法 G 将具有附加产生式 S → S1 | S2

Concatenation

如果 L1 和 L2 是无上下文语言，则 L1L2 也是无上下文的。

Example

语言 L1 和 L2 的并集，L = L1L2 = { anbncmdm }

相应的语法 G 将具有附加产生式 S → S1 S2

Kleene Star

若 L 是上下文无关语言，那么 L* 也是上下文无关语言。

Example

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

Kleene 星号 L1 = { anbn }*

对应的文法 G1 将具有附加产生式 S1 → SS1 | ε

上下文无关语言在 − 下属于 not closed

  1. Intersection − 如果 L1 和 L2 是上下文无关语言，那么 L1 ∩ L2 不一定是上下文无关语言。

  2. Intersection with Regular Language − 如果 L1 是正则语言，L2 是上下文无关语言，那么 L1 ∩ L2 是上下文无关语言。

  3. Complement − 如果 L1 是上下文无关语言，那么 L1' 可能不是上下文无关语言。