Regularne zestawy
Każdy zestaw, który reprezentuje wartość wyrażenia regularnego, nazywany jest a Regular Set.
Właściwości zestawów regularnych
Property 1. Suma dwóch regularnych zbiorów jest regularna.
Proof -
Weźmy dwa wyrażenia regularne
RE 1 = a (aa) * i RE 2 = (aa) *
Więc L 1 = {a, aaa, aaaaa, .....} (ciągi o nieparzystej długości z wyłączeniem Null)
i L 2 = {ε, aa, aaaa, aaaaaa, .......} (ciągi o parzystej długości, w tym Null)
L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, .......}
(Ciągi wszystkich możliwych długości, w tym Null)
RE (L 1 ∪ L 2 ) = a * (co samo jest wyrażeniem regularnym)
Hence, proved.
Property 2. Przecięcie dwóch regularnych zbiorów jest regularne.
Proof -
Weźmy dwa wyrażenia regularne
RE 1 = a (a *) i RE 2 = (aa) *
A więc L 1 = {a, aa, aaa, aaaa, ....} (ciągi znaków o wszystkich możliwych długościach z wyłączeniem wartości Null)
L 2 = {ε, aa, aaaa, aaaaaa, .......} (ciągi o parzystej długości, w tym Null)
L 1 ∩ L 2 = {aa, aaaa, aaaaaa, .......} (ciągi o parzystej długości z wyłączeniem Null)
RE (L 1 ∩ L 2 ) = aa (aa) *, które samo w sobie jest wyrażeniem regularnym.
Hence, proved.
Property 3. Uzupełnienie regularnego zestawu jest regularne.
Proof -
Weźmy wyrażenie regularne -
RE = (aa) *
A więc L = {ε, aa, aaaa, aaaaaa, .......} (ciągi o parzystej długości, w tym Null)
Uzupełnienie L to wszystkie ciągi, których nie ma L.
A więc L '= {a, aaa, aaaaa, .....} (ciągi o nieparzystej długości z wyłączeniem Null)
RE (L ') = a (aa) *, które samo w sobie jest wyrażeniem regularnym.
Hence, proved.
Property 4. Różnica między dwoma regularnymi zestawami jest regularna.
Proof -
Weźmy dwa wyrażenia regularne -
RE 1 = a (a *) i RE 2 = (aa) *
A więc L 1 = {a, aa, aaa, aaaa, ....} (ciągi znaków o wszystkich możliwych długościach z wyłączeniem wartości Null)
L 2 = {ε, aa, aaaa, aaaaaa, .......} (ciągi o parzystej długości, w tym Null)
L 1 - L 2 = {a, aaa, aaaaa, aaaaaaa, ....}
(Ciągi wszystkich nieparzystych długości z wyłączeniem Null)
RE (L 1 - L 2 ) = a (aa) *, które jest wyrażeniem regularnym.
Hence, proved.
Property 5. Odwrócenie regularnego zestawu jest regularne.
Proof -
Musimy to udowodnić LR jest również regularne, jeśli L to zwykły zestaw.
Niech, L = {01, 10, 11, 10}
RE (L) = 01 + 10 + 11 + 10
L R = {10, 01, 11, 01}
RE (L R ) = 01 + 10 + 11 + 10, co jest regularne
Hence, proved.
Property 6. Zamknięcie regularnego zestawu jest regularne.
Proof -
Jeśli L = {a, aaa, aaaaa, .......} (ciągi o nieparzystej długości z wyłączeniem Null)
tj. RE (L) = a (aa) *
L * = {a, aa, aaa, aaaa, aaaaa, ……………} (ciągi wszystkich długości z wyłączeniem wartości Null)
RE (L *) = a (a) *
Hence, proved.
Property 7. Łączenie dwóch regularnych zestawów jest regularne.
Proof −
Niech RE 1 = (0 + 1) * 0 i RE 2 = 01 (0 + 1) *
Tutaj L 1 = {0, 00, 10, 000, 010, ......} (zbiór ciągów kończących się na 0)
i L 2 = {01, 010,011, .....} (zbiór ciągów zaczynających się od 01)
Wówczas L 1 L 2 = {001,0010,0011,0001,00010,00011,1001,10010, .............}
Zbiór ciągów zawierający 001 jako podciąg, który może być reprezentowany przez RE - (0 + 1) * 001 (0 + 1) *
Stąd udowodniono.
Tożsamości związane z wyrażeniami regularnymi
Biorąc pod uwagę R, P, L, Q jako wyrażenia regularne, następujące tożsamości posiadają -
- ∅ * = ε
- ε * = ε
- 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 (tożsamość związku)
- R ε = ε R = R (tożsamość dla konkatenacji)
- ∅ L = L ∅ = ∅ (anihilator dla konkatenacji)
- R + R = R (prawo idempotentne)
- L (M + N) = LM + LN (Lewe prawo dystrybucji)
- (M + N) L = ML + NL (prawo rozdzielcze)
- ε + RR * = ε + R * R = R *