OPERACIONES CON LENGUAJES

El concepto de concatenación se puede extender a los lenguajes. Se define la concatenación de lenguajes como sigue:

El lenguaje que resulta de la concatenación de A y B está formado por la concatenación de todas las cadenas de A con todas las cadenas de B.
Ejemplo: Si 

                  y 

 entonces, 

 

La concatenación de lenguajes se puede realizar aún si los lenguajes no están construidos sobre el mismo alfabeto, en tal caso la concatenación nos lleva a que, si A y B, son lenguajes sobre ∑1 y ∑2, entonces el lenguaje resultante será un lenguaje sobre ∑1U∑2. 

La cadena vacía se comporta como la identidad en cuanto a la concatenación de lenguajes se trata, ya que si tenemos

 . 

La definición de potencia, también puede extenderse a los lenguajes de la misma manera

Por lo tanto, si 

 sobre un algún alfabeto, se tiene que

Hay que destacar que de la anterior definición se tiene que 

. 
Dado que los lenguajes son conjuntos de cadenas, las operaciones, intersección, unión y sublenguaje se definen como sigue:

Sean A y B lenguajes sobre el alfabeto ∑, la unión se denota como A U B y quiere decir que el lenguaje resultante esta formado por todas la palabras que se encuentren en al menos uno de los dos lenguajes, más generalmente:

La intersección de los lenguajes A y B es un lenguaje formado por todas las cadenas que se encuentran tanto en A como en B, esto es:

Con un ejemplo se prodrá ilustrar mejor las dos definiciones anteriores. 

                                  y

Ejemplo: Sean  

                                                         

                       

               

Ahora hay que definir el concepto de sublenguaje, recordando la teoría de conjuntos sabemos que un conjunto W es un subconjunto de U, si U contiene a todos los elementos de W y se denota como , y se lee, W es un subconjunto de U. Esta definición se puede mudar perfectamente a la teoría de lenguajes, diciendo que si A y B son lenguajes, entonces B es un sublenguaje de A, si A contiene todas las cadenas de B y se denota , y se lee B es un sublenguaje de A. 

Sea L cualquier lenguaje sobre ∑, entonces , ya que ∑* contiene todas las cadenas que son posibles de generar con el alfabeto ∑. 

La igualdad de lenguajes cumple con las mismas características que la igualdad entre conjuntos, sean A y B lenguajes, son iguales, sólo si, contienen exactamente las mismas cadenas. También hereda sus propiedades de la teoría de conjunto.

·        Sean A y B, lenguajes sobre ∑, A = B, solo si  y . Sirve para demostrar la igualdad entre lenguajes y se utiliza para demostrar que la concatenación es distributiva con respecto a la unión de lenguajes. 

Demostración. Supongamos que A = B, entonces tenemos que probar que 

y, para ello digamos que x ϵ A . Como B contiene las mismas cadenas que A, diremos que x ϵ B, de lo que se deduce que . De la misma forma, si x ϵ B, entonces x ϵ A ya que los dos contienen las mismas cadenas, de lo anterior tenemos que , lo cual no lleva a que y. Esto significa que las cadenas que están en B, están también en A y viceversa, por lo que A = B, con lo que se demuestra la igualdad.   

  Dados los lenguajes A,B y C, sobre un alfabeto ∑, se cumple que:

1.     

2.     

Demostración. Para demostrar la primera parte del teorema, probaremos primero que. Supongamos que , y que x = w*y, donde w ϵ A y yϵ B U C. Sí y ϵ B, tenemos que x = w* y ϵ A* B y por lo tanto x ϵ A * B U A * C. Si y ϵ C, tenemos que x ϵ A* C y de nuevo x ϵ A* B U A*C. Sin importar a que lenguaje pertenesca y, se deduce que

Ahora para probar  suponemos que x ϵ A* B U A * C

de modo que x ϵ A * B o x ϵ A * C. Si x ϵ A * B y x = u*v donde u ϵ A y u ϵ B, tenemos que u ϵ B U C, y ya que u ϵ A, tenemos que x ϵ A * ( B U C). Por otro lado si x ϵ A * C y si x = w * y, tenemos que w ϵ A y y ϵ C, por lo tanto y ϵ B U C y ya que w ϵ A, tenemos que x ϵ A * (B U C). De lo anterior se deduce que . Se obtiene que , lo que demuestra la igualdad.

De forma muy similar se demuestra la segunda parte así que no aparecerá la demostración en este documento. 

A diferencia de la unión, la concatenación no es distributiva con respecto a la intersección de lenguajes, para esto, hay que proponer que, si A = {a, ϵ}, B = {ϵ } y  C = { a }, entonces A * B = {a,ϵ} y , por lo que . Pero tenemos que , entonces , por lo tanto:

Ahora veremos dos conceptos más, el primero es el de cerradura de Kleene o cerradura estrella, élla esta definida como la unión de 0 o más potencias de un lenguaje A sobre un alfabeto ∑, más precisamente, la cerradura de Kleene es realizar 0 o más concatenaciones del lenguaje A con él mismo, y se denota , lo que resulta en un lenguaje que contiene todas las cadenas que son posibles de formar sobre ∑. También tenemos a la cerradura positiva, que es la unión de una o más potencias de A en ∑, resultando en un lenguaje que contiene, todas las cadenas excepto la cadena vacía ϵ, y se denota .

Un factor importante que debe recordarse es que la diferencia entre estos dos tipos de cerradura es, que en la cerradura de Kleene se realiza con 0 o más concatenaciones, en cambio la cerraduta positiva se realiza con  o más concatenaciones.


Ejemplo: Si ∑ es el alfabeto español y A = {a} sobre ∑, tendremos que, ya que  y . 

La definición de la cerradura de Kleene es igual a la del lenguaje universal. Sea ∑ un alfabeto, es la concatenación de 0 o más símbolos de ∑, que son las cadenas que conforman el lenguaje universal que también se denota ∑*, de aquí que todo lenguaje sobre ∑ es un sublenguaje de ∑*.

La diferencia entre lenguajes sigue las mismas reglas que para la diferencia en conjuntos, es decir, si A y B son lenguajes sobre ∑, entonces , que resulta en un lenguaje que contiene todas las cadenas de A, que no están en B.

Al igual que con conjuntos se puede definir el completo de un lenguaje. Sea A un lenguaje sobre ∑ su complemento es