Automata Theory 简明教程

Property 1 . 两个正则集的并集是正则。

Proof −

让我们取两个正则表达式

RE1 = a(aa)，RE2 = (aa)

所以，L1 = {a, aaa, aaaaa,…​..}（不包括 Null 的奇数长度字符串）

且 L2 ={ ε, aa, aaaa, aaaaaa,…​…​.} （包括 Null 的偶数长度字符串）

L1 ∪ L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,…​…​.}

（包括 Null 的所有可能长度的字符串）

RE (L1 ∪ L2) = a* （本身就是一个正则表达式）

Hence, proved.

Property 2. 两个正则集的交集是正则。

Proof −

让我们取两个正则表达式

RE1 = a(a*)，RE2 = (aa)*

所以，L1 = { a,aa, aaa, aaaa, …​.} （不包括 Null 的所有可能长度字符串）

L2 = { ε, aa, aaaa, aaaaaa,…}（包含空字符串的偶数长度字符串）

L1 ∩ L2 = { aa, aaaa, aaaaaa,…}（不包含空字符串的偶数长度字符串）

RE (L1 ∩ L2) = aa(aa)*，本身是一个正则表达式。

Hence, proved.

Property 3. 一个正则集合的补集是正则的。

Proof −

我们取正则表达式−

RE = (aa)*

所以，L = {ε, aa, aaaa, aaaaaa, …}（包含空字符串的偶数长度字符串）

L 的补集是不在 L 中的所有字符串。

所以，L’ = {a, aaa, aaaaa, …}（不包含空字符串的奇数长度字符串）

RE (L’) = a(aa)*，本身是一个正则表达式。

Hence, proved.

Property 4. 两个正则集合的差是正则的。

Proof −

我们取两个正则表达式−

RE1 = a (a*) 和 RE2 = (aa)*

所以，L1 = {a, aa, aaa, aaaa, …}（包含所有可能的长度且不包含空字符串的字符串）

L2 = { ε, aa, aaaa, aaaaaa,…}（包含空字符串的偶数长度字符串）

L1 – L2 = {a, aaa, aaaaa, aaaaaaa, …}

（不包含空字符串的所有奇数长度字符串）

RE (L1 – L2) = a (aa)*，是一个正则表达式。

Hence, proved.

Property 5. 一个正则集合的反转是正则的。

Proof −

我们要证明 LR 也是正则的，如果 L 是一个正则集合。

令 L = {01，10，11，10}

RE (L) = 01 + 10 + 11 + 10

LR = {10，01，11，01}

RE (LR) = 01 + 10 + 11 + 10 为正则语言

Hence, proved.

Property 6. 正则集合的闭包为正则语言。

Proof −

如果 L = {a, aaa, aaaaa, …​…​.} （长度为奇数且不含空集合的字符串），

即 RE (L) = a (aa)*

L* = {a, aa, aaa, aaaa , aaaaa,……………} （长度可为任意正整数且不含空集合的字符串）

RE (L*) = a (a)*

Hence, proved.

Property 7. 两个正则集合的连接为正则语言。

Proof −

令 RE1 = (0+1) 0 and RE2 = 01(0+1)

此处，L1 = {0, 00, 10, 000, 010, …​…​} （以 0 结尾的字符串集合）

且 L2 = {01, 010,011,…​..} （以 01 开头的字符串集合）

则 L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,…​…​…​…​.}

包含 001 作为子串的字符串集合，可以用正则表达式表示为 − (0 + 1) 001(0 + 1)

因此得证。

给出正则表达式 R, P, L, Q，则有如下恒等式：