Álgebra de las expresiones regulares

De Wikiversidad

Asociatividad y conmutatividad.[editar]

Existen un conjunto de leyes algebraicas que se pueden utilizar para las expresiones regulares:

  • Ley conmutativa para la unión: L+M = M+L:
  • Ley asociativa para la unión (L+M) + N: L+ (M+N)
  • Ley asociativa para la concatenación: (LM)N = L(MN)

Elemento identidad y Elemento nulo.[editar]

Una identidad para un operador es un valor tal que cuando el operador se aplica a la identidad y a algún otro valor, el resultado es el otro valor.

  • 0 es la identidad para la adición: 0 + x = x + 0 = x.
  • 1 es la identidad para la multiplicación: 1 × x = x × 1 = x
  • ∅ es la identidad para la unión: ∅ + L = L + ∅= L
  • 𝜖 es la identidad para la concatenación: 𝜖L= L 𝜖 = L
  • ∅ es el identidad para la concatenación: ∅L= L∅ = ∅

Leyes distributivas.[editar]

Como la concatenación no es conmutativa, tenemos dos formas de la ley distributiva para la concatenación:

  • Ley Distributiva Izquierda para la concatenación sobre unión: L(M + N) = LM + LN
  • Ley Distributiva Derecha para la concatenación sobre unión: (M + N)L = ML + NL

Leyes de idempotencia[editar]

Se dice que un operador es idempotente (idempotent) si el resultado de aplicarlo a dos argumentos con el mismo valor es el mismo valor

  • la suma no es un operador idempotente: x + x ≠ x (aunque para algunos valores si aplica como 0 + 0 = 0)
  • En general la multiplicación tampoco es idempotente: x × x ≠ x
  • La unióne intersección son ejemplos comunes de operadores idempotentes. Ley idempotente para la unión: L + L = L