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.
Una de las equivalencias vistas anteriormente dice: “Un LF es Regular si puede ser representado mediante una ER”.
En esta sección analizaremos diversas propiedades que tienen los LRs, y las relacionaremos con las ERs.
Teniendo en cuenta que los LFs son conjuntos, las operaciones entre conjuntos –como la unión, la intersección y el complemento– se aplican también a los LRs.
Además, hay otras operaciones propias de los LFs –como la concatenación y las clausuras– que, lógicamente, se aplican al caso particular de los LRs.
Por ello, afirmamos: los LRs son cerrados bajo la unión, la concatenación, las dos clausuras (la de Kleene y la positiva), el complemento con respecto al Lenguaje Universal y la intersección. Esto es: (1) la unión de dos LRs es un LR; (2) la concatenación de dos LRs es un LR; (3) la clausura de Kleene de un LR es un LR; (4) la clausura positiva de un LR es un LR; (5) el complemento de un LR con respecto al LU es un LR; (6) la intersección de dos LRs es un LR.
Sean L1 y L2 dos LRs. Entonces, la unión de L1 con L2, que se escribe L1 U L2, es un LR que contiene todas las palabras que pertenecen a cualquiera de los dos LRs.
Si L1 es representado por una ER R1 y L2 es representado por cierta expresión R2, la unión L1 U L2 es representada por la ER R1+R2.
Ejemplo 40
Si L1 es representado por a*b y L2 es representado por la a+b*, L1 U L2 es representado por a*b + a+b*.
La concatenación de dos LRs, L1·L2 (o, simplemente, L1L2), es un LR en el que cada palabra está formada por la concatenación de una palabra de L1 con una palabra de L2. Por ende, la cardinalidad del LR concatenación es el producto de las cardinalidades de los LRs de partida.
Sea L1 = {ab, cd} y sea L2 = {aa, acc, ad}. Entonces: L1L2 = {abaa, abacc, abad, cdaa, cdacc, cdad} y su cardinalidad es 6.
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.
