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.
