Bộ thông thường
Bất kỳ tập hợp nào đại diện cho giá trị của Biểu thức chính quy được gọi là Regular Set.
Thuộc tính của Bộ thông thường
Property 1. Sự kết hợp của hai tập hợp chính quy là chính quy.
Proof -
Hãy để chúng tôi lấy hai biểu thức chính quy
RE 1 = a (aa) * và RE 2 = (aa) *
Vì vậy, L 1 = {a, aaa, aaaaa, .....} (Các chuỗi có độ dài lẻ không bao gồm Null)
và L 2 = {ε, aa, aaaa, aaaaaa, .......} (Chuỗi có độ dài chẵn bao gồm cả Null)
L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, .......}
(Các chuỗi có tất cả các độ dài có thể bao gồm cả Null)
RE (L 1 ∪ L 2 ) = a * (chính là một biểu thức chính quy)
Hence, proved.
Property 2. Giao của hai tập hợp chính quy.
Proof -
Hãy để chúng tôi lấy hai biểu thức chính quy
RE 1 = a (a *) và RE 2 = (aa) *
Vì vậy, L 1 = {a, aa, aaa, aaaa, ....} (Các chuỗi có tất cả các độ dài có thể trừ Null)
L 2 = {ε, aa, aaaa, aaaaaa, .......} (Chuỗi có độ dài chẵn bao gồm cả Null)
L 1 ∩ L 2 = {aa, aaaa, aaaaaa, .......} (Chuỗi có độ dài chẵn không kể Null)
RE (L 1 ∩ L 2 ) = aa (aa) * chính là một biểu thức chính quy.
Hence, proved.
Property 3. Phần bù của một tập hợp chính quy là chính quy.
Proof -
Hãy để chúng tôi lấy một biểu thức chính quy -
RE = (aa) *
Vì vậy, L = {ε, aa, aaaa, aaaaaa, .......} (Chuỗi có độ dài chẵn bao gồm cả Null)
Sự bổ sung của L là tất cả các chuỗi không có trong L.
Vì vậy, L '= {a, aaa, aaaaa, .....} (Chuỗi có độ dài lẻ không bao gồm Null)
RE (L ') = a (aa) * chính là một biểu thức chính quy.
Hence, proved.
Property 4. Sự khác biệt của hai tập hợp chính quy là thường xuyên.
Proof -
Chúng ta hãy lấy hai biểu thức chính quy -
RE 1 = a (a *) và RE 2 = (aa) *
Vì vậy, L 1 = {a, aa, aaa, aaaa, ....} (Các chuỗi có tất cả các độ dài có thể trừ Null)
L 2 = {ε, aa, aaaa, aaaaaa, .......} (Chuỗi có độ dài chẵn bao gồm cả Null)
L 1 - L 2 = {a, aaa, aaaaa, aaaaaaa, ....}
(Các chuỗi có độ dài lẻ không bao gồm Null)
RE (L 1 - L 2 ) = a (aa) * là một biểu thức chính quy.
Hence, proved.
Property 5. Sự đảo ngược của một tập hợp chính quy là thường xuyên.
Proof -
Chúng tôi phải chứng minh LR cũng thường xuyên nếu L là một tập hợp thông thường.
Cho, L = {01, 10, 11, 10}
RE (L) = 01 + 10 + 11 + 10
L R = {10, 01, 11, 01}
RE (L R ) = 01 + 10 + 11 + 10 là thông thường
Hence, proved.
Property 6. Việc đóng một tập hợp thông thường là thường xuyên.
Proof -
Nếu L = {a, aaa, aaaaa, .......} (Chuỗi có độ dài lẻ không bao gồm Null)
tức là RE (L) = a (aa) *
L * = {a, aa, aaa, aaaa, aaaaa, ……………} (Các chuỗi có độ dài không bao gồm Null)
RE (L *) = a (a) *
Hence, proved.
Property 7. Phép ghép của hai tập hợp chính quy là chính quy.
Proof −
Cho RE 1 = (0 + 1) * 0 và RE 2 = 01 (0 + 1) *
Ở đây, L 1 = {0, 00, 10, 000, 010, ......} (Tập hợp các chuỗi kết thúc bằng 0)
và L 2 = {01, 010,011, .....} (Tập hợp các chuỗi bắt đầu bằng 01)
Khi đó, L 1 L 2 = {001,0010,0011,0001,00010,00011,1001,10010, .............}
Tập hợp các chuỗi chứa 001 dưới dạng một chuỗi con có thể được biểu diễn bằng một RE - (0 + 1) * 001 (0 + 1) *
Do đó, đã chứng minh.
Nhận dạng Liên quan đến Biểu thức Thông thường
Với R, P, L, Q là các biểu thức chính quy, các đặc điểm sau giữ:
- ∅ * = ε
- ε * = ε
- 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 (Định danh cho liên hiệp)
- R ε = ε R = R (Đồng nhất cho phép nối)
- ∅ L = L ∅ = ∅ (Bộ hủy để nối)
- R + R = R (Luật lý tưởng)
- L (M + N) = LM + LN (Luật phân phối trái)
- (M + N) L = ML + NL (Luật phân phối phải)
- ε + RR * = ε + R * R = R *