Ensembles réguliers
Tout ensemble qui représente la valeur de l'expression régulière est appelé un Regular Set.
Propriétés des ensembles réguliers
Property 1. L'union de deux ensembles réguliers est régulière.
Proof -
Prenons deux expressions régulières
RE 1 = a (aa) * et RE 2 = (aa) *
Donc, L 1 = {a, aaa, aaaaa, .....} (Chaînes de longueur impaire excluant Null)
et L 2 = {ε, aa, aaaa, aaaaaa, .......} (Chaînes de longueur paire y compris Null)
L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, .......}
(Chaînes de toutes les longueurs possibles, y compris Null)
RE (L 1 ∪ L 2 ) = a * (qui est une expression régulière elle-même)
Hence, proved.
Property 2. L'intersection de deux ensembles réguliers est régulière.
Proof -
Prenons deux expressions régulières
RE 1 = a (a *) et RE 2 = (aa) *
Donc, L 1 = {a, aa, aaa, aaaa, ....} (Chaînes de toutes les longueurs possibles sauf Null)
L 2 = {ε, aa, aaaa, aaaaaa, .......} (Chaînes de longueur paire y compris Null)
L 1 ∩ L 2 = {aa, aaaa, aaaaaa, .......} (Chaînes de longueur paire excluant Null)
RE (L 1 ∩ L 2 ) = aa (aa) * qui est une expression régulière elle-même.
Hence, proved.
Property 3. Le complément d'un ensemble régulier est régulier.
Proof -
Prenons une expression régulière -
RE = (aa) *
Donc, L = {ε, aa, aaaa, aaaaaa, .......} (Chaînes de longueur paire y compris Null)
Complément de L est toutes les chaînes qui ne sont pas dans L.
Donc, L '= {a, aaa, aaaaa, .....} (Chaînes de longueur impaire excluant Null)
RE (L ') = a (aa) * qui est une expression régulière elle-même.
Hence, proved.
Property 4. La différence de deux séries régulières est régulière.
Proof -
Prenons deux expressions régulières -
RE 1 = a (a *) et RE 2 = (aa) *
Donc, L 1 = {a, aa, aaa, aaaa, ....} (Chaînes de toutes les longueurs possibles sauf Null)
L 2 = {ε, aa, aaaa, aaaaaa, .......} (Chaînes de longueur paire y compris Null)
L 1 - L 2 = {a, aaa, aaaaa, aaaaaaa, ....}
(Chaînes de toutes les longueurs impaires à l'exclusion de Null)
RE (L 1 - L 2 ) = a (aa) * qui est une expression régulière.
Hence, proved.
Property 5. L'inversion d'un ensemble régulier est régulière.
Proof -
Nous devons prouver LR est également régulier si L est un ensemble régulier.
Soit, L = {01, 10, 11, 10}
RE (L) = 01 + 10 + 11 + 10
L R = {10, 01, 11, 01}
RE (L R ) = 01 + 10 + 11 + 10 qui est régulier
Hence, proved.
Property 6. La fermeture d'un set régulier est régulière.
Proof -
Si L = {a, aaa, aaaaa, .......} (Chaînes de longueur impaire excluant Null)
c'est-à-dire RE (L) = a (aa) *
L * = {a, aa, aaa, aaaa, aaaaa, ……………} (chaînes de toutes les longueurs sauf Null)
RE (L *) = a (a) *
Hence, proved.
Property 7. La concaténation de deux ensembles réguliers est régulière.
Proof −
Soit RE 1 = (0 + 1) * 0 et RE 2 = 01 (0 + 1) *
Ici, L 1 = {0, 00, 10, 000, 010, ......} (Ensemble de chaînes se terminant par 0)
et L 2 = {01, 010,011, .....} (Ensemble de chaînes commençant par 01)
Ensuite, L 1 L 2 = {001,0010,0011,0001,00010,00011,1001,10010, .............}
Ensemble de chaînes contenant 001 comme sous-chaîne pouvant être représentée par un RE - (0 + 1) * 001 (0 + 1) *
Par conséquent, prouvé.
Identités liées aux expressions régulières
Étant donné R, P, L, Q comme expressions régulières, les identités suivantes sont valables -
- ∅ * = ε
- ε * = ε
- 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 (L'identité pour l'union)
- R ε = ε R = R (L'identité de la concaténation)
- ∅ L = L ∅ = ∅ (L'annihilateur pour la concaténation)
- R + R = R (loi idempotente)
- L (M + N) = LM + LN (loi distributive gauche)
- (M + N) L = ML + NL (Loi distributive droite)
- ε + RR * = ε + R * R = R *