正則集

---

---

表示正則表示式值的任何集合都稱為正則集。

正則集的性質

性質 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*