Conjuntos regulares

Cualquier conjunto que represente el valor de la expresión regular se denomina Regular Set.

Propiedades de los conjuntos regulares

Property 1. La unión de dos conjuntos regulares es regular.

Proof -

Tomemos dos expresiones regulares

RE 1 = a (aa) * y RE 2 = (aa) *

Entonces, L 1 = {a, aaa, aaaaa, .....} (cadenas de longitud impar excluyendo Null)

y L 2 = {ε, aa, aaaa, aaaaaa, .......} (cadenas de longitud uniforme incluyendo Null)

L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, .......}

(Cadenas de todas las longitudes posibles, incluido Null)

RE (L 1 ∪ L 2 ) = a * (que es una expresión regular en sí misma)

Hence, proved.

Property 2. La intersección de dos conjuntos regulares es regular.

Proof -

Tomemos dos expresiones regulares

RE 1 = a (a *) y RE 2 = (aa) *

Entonces, L 1 = {a, aa, aaa, aaaa, ....} (cadenas de todas las longitudes posibles excluyendo Null)

L 2 = {ε, aa, aaaa, aaaaaa, .......} (Cadenas de longitud uniforme incluyendo Null)

L 1 ∩ L 2 = {aa, aaaa, aaaaaa, .......} (cadenas de longitud par excluyendo Null)

RE (L 1 ∩ L 2 ) = aa (aa) * que es una expresión regular en sí misma.

Hence, proved.

Property 3. El complemento de un conjunto regular es regular.

Proof -

Tomemos una expresión regular -

RE = (aa) *

Entonces, L = {ε, aa, aaaa, aaaaaa, .......} (Cadenas de longitud uniforme incluyendo Null)

Complemento de L son todas las cadenas que no están en L.

Entonces, L '= {a, aaa, aaaaa, .....} (cadenas de longitud impar excluyendo Null)

RE (L ') = a (aa) * que es una expresión regular en sí misma.

Hence, proved.

Property 4. La diferencia de dos series regulares es regular.

Proof -

Tomemos dos expresiones regulares:

RE 1 = a (a *) y RE 2 = (aa) *

Entonces, L 1 = {a, aa, aaa, aaaa, ....} (cadenas de todas las longitudes posibles excluyendo Null)

L 2 = {ε, aa, aaaa, aaaaaa, .......} (Cadenas de longitud uniforme incluyendo Null)

L 1 - L 2 = {a, aaa, aaaaa, aaaaaaa, ....}

(Cadenas de todas las longitudes impares excluyendo Null)

RE (L 1 - L 2 ) = a (aa) * que es una expresión regular.

Hence, proved.

Property 5. La inversión de un conjunto regular es regular.

Proof -

Tenemos que probar LR también es regular si L es un conjunto regular.

Sea, L = {01, 10, 11, 10}

RE (L) = 01 + 10 + 11 + 10

L R = {10, 01, 11, 01}

RE (L R ) = 01 + 10 + 11 + 10 que es regular

Hence, proved.

Property 6. El cierre de un set regular es regular.

Proof -

Si L = {a, aaa, aaaaa, .......} (cadenas de longitud impar excluyendo Null)

es decir, RE (L) = a (aa) *

L * = {a, aa, aaa, aaaa, aaaaa, ……………} (Cadenas de todas las longitudes excluyendo Null)

RE (L *) = a (a) *

Hence, proved.

Property 7. La concatenación de dos conjuntos regulares es regular.

Proof −

Sea RE 1 = (0 + 1) * 0 y RE 2 = 01 (0 + 1) *

Aquí, L 1 = {0, 00, 10, 000, 010, ......} (conjunto de cadenas que terminan en 0)

y L 2 = {01, 010,011, .....} (Conjunto de cadenas que comienzan con 01)

Entonces, L 1 L 2 = {001,0010,0011,0001,00010,00011,1001,10010, .............}

Conjunto de cadenas que contienen 001 como una subcadena que se puede representar con RE - (0 + 1) * 001 (0 + 1) *

Por lo tanto, probado.

Identidades relacionadas con expresiones regulares

Dados R, P, L, Q como expresiones regulares, las siguientes identidades son válidas:

  • ∅ * = ε
  • ε * = ε
  • 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 (La identidad de la unión)
  • R ε = ε R = R (La identidad para la concatenación)
  • ∅ L = L ∅ = ∅ (El aniquilador para la concatenación)
  • R + R = R (ley idempotente)
  • L (M + N) = LM + LN (ley distributiva izquierda)
  • (M + N) L = ML + NL (Ley distributiva por la derecha)
  • ε + RR * = ε + R * R = R *