Conjuntos regulares

Cualquier conjunto que represente un valor de expresión regular se llama El conjunto habitual.

Propiedades de los conjuntos regulares

Propiedad 1… La unión de los dos conjuntos regulares es correcta.

Evidencia –

Tomemos dos expresiones regulares

RE1 = a (aa) * y RE2 = (aa) *

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

y L2 = {ε, aa, aaaa, aaaaaa,…….} (cadenas de longitud uniforme, incluido Null)

L1 ∪ L2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,…….}

(Cadenas de cualquier longitud posible, incluido Null)

RE (L1 ∪ L2) = a * (que a su vez es una expresión regular)

Por tanto, está probado.

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

Evidencia –

Tomemos dos expresiones regulares

RE1 = a (a *) y RE2 = (aa) *

Entonces, L1 = {a, aa, aaa, aaaa,….} (cadenas de todas las longitudes posibles, excepto Null)

L2 = {ε, aa, aaaa, aaaaaa,…….} (cadenas de longitud uniforme, incluido Null)

L1 ∩ L2 = {aa, aaaa, aaaaaa,…….} (cadenas de longitud uniforme, excluyendo Null)

RE (L1 ∩ L2) = aa (aa) *, que en sí misma es una expresión regular.

Por tanto, está probado.

Propiedad 3. La adición al conjunto regular es regular.

Evidencia –

Tomemos una expresión regular:

RE = (aa) *

Entonces L = {ε, aa, aaaa, aaaaaa,…….} (cadenas de longitud uniforme, incluido Null)

Adición L estas son todas las líneas que no están en L…

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

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

Por tanto, está probado.

Propiedad 4. La diferencia entre los dos conjuntos regulares es natural.

Evidencia –

Tomemos dos expresiones regulares:

RE1 = a (a *) y RE2 = (aa) *

Entonces, L1 = {a, aa, aaa, aaaa,….} (cadenas de todas las longitudes posibles, excepto Null)

L2 = {ε, aa, aaaa, aaaaaa,…….} (cadenas de longitud uniforme, incluido Null)

L1 – L2 = {a, aaa, aaaaa, aaaaaaa,….}

(Cadenas de cualquier longitud impar, excepto Null)

RE (L1 – L2) = a (aa) *, que es una expresión regular.

Por tanto, está probado.

Propiedad 5. El giro de un set regular es regular.

Evidencia –

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

LR = {10, 01, 11, 01}

RE (LR) = 01 + 10 + 11 + 10, que es normal

Por tanto, está probado.

Propiedad 6. El cierre de un set regular ocurre con regularidad.

Evidencia –

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

aquellos. RE (L) = a (aa) *

L * = {a, aa, aaa, aaaa, aaaaa, ……………} (cadenas de cualquier longitud, excepto Null)

RE (L *) = a (a) *

Por tanto, está probado.

Propiedad 7. La concatenación de dos conjuntos regulares es correcta.

Prueba –

Deje RE1 = (0 + 1) * 0 y RE2 = 01 (0 + 1) *

Aquí L1 = {0, 00, 10, 000, 010,……} (conjunto de líneas que terminan en 0)

y L2 = {01, 010,011,…..} (conjunto de filas que comienza en 01)

Entonces L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,………….}

Un conjunto de cadenas que contiene 001 como una subcadena que se puede representar por RE – (0 + 1) * 001 (0 + 1) *

Por tanto, está probado.

Identidades de expresión regular

Teniendo en cuenta que R, P, L, Q son expresiones regulares, se cumplen las siguientes identidades:

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

En Este Curso

🚫