Automata Theory 简明教程

CFL Closure Property

无上下文语言在 − 下为 closed

Context-free languages are closed under −

  1. Union

  2. Concatenation

  3. Kleene Star operation

Union

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

Let L1 and L2 be two context free languages. Then L1 ∪ L2 is also context free.

Example

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

Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab

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

Let L2 = { cmdm , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε

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

Union of L1 and L2, L = L1 ∪ L2 = { anbn } ∪ { cmdm }

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

The corresponding grammar G will have the additional production S → S1 | S2

Concatenation

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

If L1 and L2 are context free languages, then L1L2 is also context free.

Example

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

Union of the languages L1 and L2, L = L1L2 = { anbncmdm }

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

The corresponding grammar G will have the additional production S → S1 S2

Kleene Star

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

If L is a context free language, then L* is also context free.

Example

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

Let L = { anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε

Kleene 星号 L1 = { anbn }*

Kleene Star L1 = { anbn }*

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

The corresponding grammar G1 will have additional productions S1 → SS1 | ε

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

Context-free languages are not closed under −

  1. Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily context free.

  2. Intersection with Regular Language − If L1 is a regular language and L2 is a context free language, then L1 ∩ L2 is a context free language.

  3. Complement − If L1 is a context free language, then L1’ may not be context free.