正则集

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

正则集的属性

属性 1。 两个正则集的并集是正则的。

证明 −

让我们取两个正则表达式

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

因此，L₁ = {a, aaa, aaaaa,.....} (奇数长度的字符串，不包括 Null)

并且 L₂ ={ ε, aa, aaaa, aaaaaa,.......} (偶数长度的字符串，包括 Null)

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

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

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

因此，得到证明。

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

证明 −

让我们取两个正则表达式

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

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

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

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

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

因此，得到证明。

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

证明 −

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

RE = (aa)*

因此，L = {ε, aa, aaaa, aaaaaa, .......}（包括 Null 在内的偶数长度字符串）

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

因此，L' = {a, aaa, aaaaa, .....}（不包括 Null 的奇数长度字符串）

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

因此，得到证明。

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

证明 −

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

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

因此，L₁ = {a, aa, aaa, aaaa, ....} (所有可能长度的字符串，不包括 Null)

L₂ = { ε, aa, aaaa, aaaaaa,.......} (偶数长度的字符串，包括 Null)

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

(所有奇数长度的字符串，不包括Null)

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, .......} (奇数长度的字符串不包括 Null)

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

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

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*