Álgebra de las expresiones regulares

Asociatividad y conmutatividad.

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.

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.

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

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