Operaciones sobre lenguajes regulares, generalidades, unión de lenguajes regulares, concatenación de lenguajes regulares, clausura de Kleene de un lenguaje regular, clausura positiva de un lenguaje regular, complemento de un lenguaje regular, intersección de dos lenguajes regulares.
Si L1 es representado por una ER R1 y L2 es representado por R2, entonces la concatenación L1L2 es representada por la ER R1R2.
Ejemplo 42
Si L1 es representado por a*b y L2 es representado por a+b*, la concatenación L1L2 es representada por la ER a*b(a+b*). Concatenando una palabra de a*b, como aab, con una palabra de a+b*, como bb, se obtiene aabbb, que es una palabra del LR concatenación.
Si L es un LR, su clausura de Kleene, L*, es un LR infinito (salvo una excepción) formado por: (1) la palabra vacía, (2) las palabras de L y (3) todas aquellas palabras que se obtienen concatenando palabras de L, un número arbitrario de veces.
La excepción es si el LR está formado solo por la palabra vacía.
Sea L = {ab, ba}. Entonces, L* = {ε, ab, ba, abab, abba, baba, ababab, ababba, abbaba, bababa, …}.
Si L es representado por la ER R, L* es representado por R*.
Ejemplo 44
Si L es representado por a*b, L* es representado por (a*b)*. Las palabras ε, aab, aabab, babaabb pertenecen al lenguaje L*.
Si L es un LR, su clausura positiva, L+, es un LR formado por las palabras de L y todas aquellas palabras que se obtienen concatenando palabras de L, un número arbitrario de veces.
Si L es representado por R, L+ es representado por R+.
Si L es representado por a*b, L+ es representado por (a*b)+. Las palabras aab, aabab, babaabb pertenecen al lenguaje L+.
** La clausura positiva de un LR contiene a la palabra vacía solo si ésta pertenece al lenguaje original.
El complemento de un LR con respecto al LU, Lc, es un LR que está formado por todas aquellas palabras que no pertenecen al lenguaje original.
Sea el alfabeto {a, b}.
Si L es representado por la ER (a+b)+, o sea, la ERU “menos” la palabra vacía, entonces Lc solo contiene a la palabra vacía.
Si L es a(a+b)*, es decir, el LR formado por todas las palabras que comienzan con a, entonces Lc es b(a+b)* + ε.
Nota 6: No existen operadores para describir el complemento de una ER, aunque en algunos casos se utiliza not.
Dado que los lenguajes son conjuntos, se pueden aplicar sobre ellos las operaciones propias de los conjuntos. El complemento y la intersección son dos de ellas.
Lo más importante es que la aplicación de estas operaciones, muy útiles para trabajar con lenguajes difíciles de definir de otra manera, produce lenguajes que siguen siendo Regulares.
La intersección de dos LRs es un LR constituido por todas aquellas palabras que pertenecen a los dos lenguajes dados.
Sea el alfabeto {a, b}.
Si L1 es a(a + b)* [todas las palabras que comienzan con a] y L2 es (a + b)*b [todas las palabras que terminan con b], entonces L1 ∩ L2 es a(a + b)*b [todas las palabras que comienzan con a y terminan con b].
Nota 7: No existen operadores para describir la intersección de dos ERs.
