正则集

---

---

表示正则表达式值的任何集合都称为正则集。

正则集的性质

性质 1. 两个正则集的并集是正则的。

证明 −

让我们取两个正则表达式

RE₁ = a(aa)* 和 RE₂ = (aa)*

所以，L₁ = {a, aaa, aaaaa,.....}（奇数长度字符串，不包括空串）

和 L₂ ={ ε, aa, aaaa, aaaaaa,.......}（偶数长度字符串，包括空串）

L₁ ∪ L₂ = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,.......}

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

RE (L₁ ∪ L₂) = a* (它本身就是一个正则表达式)

因此，得证。

性质 2. 两个正则集的交集是正则的。

证明 −

让我们取两个正则表达式

RE₁ = a(a*) 和 RE₂ = (aa)*

所以，L₁ = { a,aa, aaa, aaaa, ....}（所有可能长度的字符串，不包括空串）

L₂ = { ε, aa, aaaa, aaaaaa,.......}（偶数长度字符串，包括空串）

L₁ ∩ L₂ = { aa, aaaa, aaaaaa,.......}（偶数长度字符串，不包括空串）

RE (L₁ ∩ L₂) = aa(aa)*，它本身就是一个正则表达式。

因此，得证。

性质 3. 正则集的补集是正则的。

证明 −

让我们取一个正则表达式 −

RE = (aa)*

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

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

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

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

因此，得证。

性质 4. 两个正则集的差集是正则的。

证明 −

让我们取两个正则表达式 −

RE₁ = a (a*) 和 RE₂ = (aa)*

所以，L₁ = {a, aa, aaa, aaaa, ....}（所有可能长度的字符串，不包括空串）

L₂ = { ε, aa, aaaa, aaaaaa,.......}（偶数长度字符串，包括空串）

L₁ – L₂ = {a, aaa, aaaaa, aaaaaaa, ....}

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

RE (L₁ – L₂) = a (aa)*，它是一个正则表达式。

因此，得证。

性质 5. 正则集的反转是正则的。

证明 −

如果L 是一个正则集，我们必须证明L^R 也是正则的。

例如，L = {01, 10, 11, 10}

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

L^R = {10, 01, 11, 01}

RE (L^R) = 01 + 10 + 11 + 10，它是正则的

因此，得证。

性质 6. 正则集的闭包是正则的。

证明 −

如果 L = {a, aaa, aaaaa, .......} (奇数长度字符串，不包括空串)

即， RE (L) = a (aa)*

L* = {a, aa, aaa, aaaa , aaaaa,……………} (所有长度的字符串，不包括空串)

RE (L*) = a (a)*

因此，得证。

性质 7. 两个正则集的连接是正则的。

证明 −

设 RE₁ = (0+1)*0 和 RE₂ = 01(0+1)*

这里， L₁ = {0, 00, 10, 000, 010, ......} (以 0 结尾的字符串集)

和 L₂ = {01, 010,011,.....} (以 01 开头的字符串集)

然后， L₁ L₂ = {001,0010,0011,0001,00010,00011,1001,10010,.............}

包含 001 作为子串的字符串集，可以用一个 RE 表示 − (0 + 1)*001(0 + 1)*

因此，得证。

与正则表达式相关的恒等式

给定 R、P、L、Q 为正则表达式，以下恒等式成立 −

• ∅* = ε
• ε* = ε
• RR* = R*R
• R*R* = R*
• (R*)* = R*
• RR* = R*R
• (PQ)*P =P(QP)*
• (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*
• R + ∅ = ∅ + R = R (并集的恒等式)
• R ε = ε R = R (连接的恒等式)
• ∅ L = L ∅ = ∅ (连接的零元)
• R + R = R (幂等律)
• L (M + N) = LM + LN (左分配律)
• (M + N) L = ML + NL (右分配律)
• ε + RR* = ε + R*R = R*