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 *