1.4.2 Lenguajes, operaciones con lenguajes

Los lenguajes son conjuntos de palabras, por lo tanto se pueden realizar operaciones entre ellos como ser unión, intersección, producto y diferencia.

Concatenación de lenguajes:

La concatenación entre lenguajes también es una operación y esta definida como external image gif.latex?L_%7B1%7D%5Cbullet%20L_%7B2%7D, escrito en extensión esto sería igual a:
external image gif.latex?L_%7B1%7D%5Cbullet%20L_%7B2%7D%20=%20%5Cleft%20%5C%7B%20w%20%5Cmid%20w=xy,%20x%5Cin%20L_%7B1%7D,%20y%5Cin%20L_%7B2%7D%20%5Cright%20%5C%7D
Lo que se entiende como que "external image gif.latex?x", "external image gif.latex?y" son dos caracteres; "external image gif.latex?x"pertenece al lenguaje external image gif.latex?L_%7B1%7D y "external image gif.latex?y" pertenece al lenguaje external image gif.latex?L_%7B2%7D. "external image gif.latex?w" llegaría a ser "external image gif.latex?x" concatenación "external image gif.latex?y".
Para calcular la concatenación de dos lenguajes se debe concatenar cada palabra del primero con las del segundo.
Ejemplos:
external image gif.latex?L_%7B1%7D=%5Cleft%20%5C%7B%20me,%20ro%20%5Cright%20%5C%7D%20;%20L_%7B2%7D=%5Cleft%20%5C%7B%20ta,sa%20%5Cright%20%5C%7D
external image gif.latex?CONCATENACI%C3%93N=%20%5Cleft%20%5C%7B%20meta,%20mesa,%20rota,%20rosa%20%5Cright%20%5C%7D
Una operación más complicadaes la "Estrella de Kleene" o también llamada "Cerradura de Kleene". Su definición nos dice que si L es un lenguaje su cerradura de Kleene sera su conjunto más pequeño denotado por L* qu contiene los siguientes elementos:
- La palabra vacía external image gif.latex?%5Cvarepsilon
- El conjunto external image gif.latex?L
- Todas las palabras formadas por la concatenación de miembros de external image gif.latex?L%5E%7B*%7D.
Ejemplos:
Siexternal image gif.latex?L=%20%5Cleft%20%5C%7B%20abra,cadabra%20%5Cright%20%5C%7D;%20L%5E%7B*%7D=%5Cleft%20%5C%7B%20%5Cvarepsilon%20,abra,abraabra,abracadabra,cadaabraabra%20...%20%5Cright%20%5C%7D