Operaciones con lenguajes

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

$$A\cdot B=\{a\cdot b\vert\ a\ \in A\ \textmd{y}\ b\ \in\ B\}$$

El lenguaje que resulta de la concatenación de $A$ y $B$ esta formado por la concatenación de todas la cadenas de $A$ con todas la cadenas de $B$.
Ejemplo: Si $A=\{hola,\ adios\}$ y $B=\{casa\}$, entonces, $A\cdot B=\{holacasa,\ adioscasa\}$.
La concatenación de lenguajes se puede realizar aún si los lenguajes no estan contruídos sobre el mismo alfabeto, en tal caso la concatenación nos lleva a que, si $A$ y $B$, son lenguajes sobre $\Sigma_1$ y $\Sigma_2$, entonces el lenguaje resultante será un lenguaje sobre $\Sigma_1\cup\Sigma_2$.
La cadena vacía se comporta como la identidad en cuanto a la concatenación de lenguajes se trata, ya que si tenemos $A\cdot\{\varepsilon\}=\{\varepsilon\}\cdot A=A$.
La definición de potencia, también puede extenderse a los lenguajes de la misma manera

$$\begin{array}{ll} A^n= & \left\{ \begin{array}{ll} \{\vareps... ...t A^{n-1}, & \textrm{si}\ n\geq0 \end{array}\right. \end{array}$$

Por lo tanto, si $A=\{ab\}$ sobre un algún alfabeto, se tiene que

$$\begin{array}{l} A^0=\{\varepsilon\}\\ A^1=A=\{ab\}\\ A^2=A\cdot A^1=\{abab\}\\ A^3=A\cdot A^2=\{ababab\} \end{array}$$

Hay que destacar que de la anterior definición se tiene que $\emptyset^0=\{\varepsilon\}$.
Dado que los lenguajes son conjuntos de cadenas, las operaciones, intersección, unión y sublenguaje se difinen como sigue:

Sean $A$ y $B$ lenguajes sobre el alfabeto $\Sigma$, la unión se denota como $A\cup 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:

$$A\cup B=\{x\mid x\ \in\ A \textrm{ o }x\ \in\ B\}.$$

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:

$$A\cap B=\{x\mid x\ \in\ A \textrm{ y } x\ \in\ B\}$$

Con un ejemplo se prodrá ilustrar mejor las dos definiciones anteriores.
Ejemplo: Sean $A=\{\varepsilon,a,b,c,d,e\}$ y $B=\{\varepsilon,0,1,2,3,4\}$,

$$A\cup B= \{\varepsilon,a,b,c,d,e,f,0,1,2,3,4\}\ \textrm{y}$$

$$A\cap B=\{\varepsilon\}.$$

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 $W\subseteq U$, 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 $B\subseteq A$, y se lee B es un sublenguaje de A.
Sea $L$ cualquier lenguaje sobre $\Sigma$, entonces $L\subseteq \Sigma^*$, ya que $\Sigma^*$ contiene todas las cadenas que son posibles de generar con el alfabeto $\Sigma$.
La igualdad de lenguajes cumple con las mismas caracteríscas 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 conjuntos, tales como son los siguientes teoremas:

Teorema 2.3.1   Sean $A$ y $B$, lenguajes sobre $\Sigma$, $A=B$, solo si $A\subseteq B$ y $B\subseteq A$.

El teorema 2.3.1 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$, entónces tenemos que probar que $A\subseteq B$ y $B\subseteq A$, para ello digamos que $x\in A$. Como $B$ contiene las mismas cadenas que $A$, diremos que $x\in B$, de lo que se deduce que $A\subseteq B$. De la misma forma, si $x\in B$, entónces $x\in A$ ya que los dos contienen las mismas cadenas, de lo anterior tenemos que $B\subseteq A$, lo cual no lleva a que $A\subseteq B$ y $B\subseteq A$. Esto significa que las cadenas que estan en $B$, están también en $A$ y viceversa, por lo que $A=B$, con lo que se demuestra la igualdad.    $\Box$

Teorema 2.3.2   Dados los lenguajes $A,B$ y $C$, sobre un alfabeto $\Sigma$, se cumple que:

1. $A\cdot (B\cup C)= A\cdot B\cup A\cdot C$
2. $(B\cup C)\cdot A= B\cdot A\cup C\cdot A$

Demostración.Para demostrar la primera parte del teorema, probaremos primero que $A\cdot (B\cup C)\subseteq A\cdot B\cup A\cdot C$. Supongamos que $x\in A\cdot (B\cup C)$, y que $x=w\cdot y$, donde $w\in A$ y $y\in B\cup C$. Sí $y \in B$, tenemos que $x=w\cdot y \in A\cdot B$ y por lo tanto $x\in A\cdot B\cup A\cdot C$. Si $y\in C$, tenemos que $x\in A\cdot C$ y de nuevo $x\in A\cdot B\cup A\cdot C$. Sin importar a que lenguaje pertenesca $y$, se deduce que

$$A\cdot (B\cup C) \subseteq A\cdot B\cup A\cdot C$$

Ahora para probar $A\cdot B\cup A\cdot C\subseteq A\cdot (B\cup C)$ suponemos que $x\in A\cdot B\cup A\cdot C$ de modo que $x\in A\cdot B$ o $x\in A\cdot C$. Si $x\in A\cdot B$ y $x=u\cdot v$ donde $u\in A$ y $v\in B$, tenemos que $v\in B\cup C$, y ya que $u\in A$, tenemos que $x\in A\cdot (B\cup C)$. Por otro lado si $x\in A\cdot C$ y si $x=w\cdot y$, tenemos que $w\in A$ y $y\in C$, por lo tanto $y\in B\cup C$ y ya que $w\in A$, tenemos que $x\in A\cdot (B\cup C)$. De lo anterior se deduce que $A\cdot B\cup A\cdot C\subseteq A\cdot (B\cup C)$. Utilizando el teorema 2.3.1 se obtiene que $A\cdot B\cup A\cdot C = A\cdot(B\cup C)$, lo que demuestra la igualdad.    $\Box$

De forma muy similar se demuestra la segunda parte del teorema 2.3.2. 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,\varepsilon\}$, $B=\{\varepsilon\}$ y $C=\{a\}$, entoces $A\cdot B=\{a,\varepsilon\}$ y $A\cdot C=\{a^2,a\}$, por lo que $A\cdot B\cap A\cdot C=\{a\}$. Pero tenemos que $B\cap C=\emptyset$, entonces $A\cdot (B\cap C)=\emptyset$, por lo tanto:

$$A\cdot B\cap A\cdot C=\{a\}\neq\emptyset=A\cdot (B\cap C)$$

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 $\Sigma$, más precisamente, la cerradura de Kleene es realizar 0 o más concatenaciones del lenguaje $A$ con él mismo, y se denota $A^*=\cup_{n=0}^\infty A^n$, lo que resulta en un lenguaje que contiene todas las cadenas que son posibles de formar sobre $\Sigma$. También tenemos a la cerradura positiva, que es la unión de una o más potencias de $A$ en $\Sigma$, resultando en un lenguaje que contiene, todas las cadenas excepto la cadena vacía $\varepsilon$, y se denota $A^+=\cup_{n=1}^\infty A^n$.

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 $1$ o más concatenaciones.
Ejemplo: Si $\Sigma$ es el alfabeto español y $A=\{a\}$ sobre $\Sigma$, tendremos que $A^*=\cup_{n=0}^\infty A^n=\{\varepsilon,a,a^2,\ldots\}$, ya que $A^0=\{\varepsilon \}$ y $A^+=\cup_{n=1}^\infty A=\{a,a^2,a^3,\ldots\}$.
La definición de la cerradura de Kleene es igual a la de el lenguaje universal, mencionada en la sección 2.4 en la página . Sea $\Sigma$ un alfabeto, $\Sigma^*=\cup_{i=0}^\infty\Sigma$ es la concatenación de 0 o más símbolos de $\Sigma$, que son las cadenas que conforman el lenguaje universal que también se denota $\Sigma^*$, de aquí que todo lenguaje sobre $\Sigma$ es un sublenguaje de $\Sigma^*$.
La diferencia entre lenguajes sigue las mismas reglas que para la diferencia en conjuntos, es decir, si $A$ y $B$ son lenguajes sobre $\Sigma$, entonces $A-B=\{x\mid x\in A\ \mathrm{y}\ x\notin\ B\}$, que resulta en un lenguaje que contiene todas las cadenas de $A$, que no estan en $B$.
Al igual que con conjutos se puede definir el complento de un lenguaje. Sea $A$ un lenguaje sobre $\Sigma$ su complemento es

$$\overline{A}=\Sigma^*-A$$

se puede que ver la definición se plantea de la misma manera que con conjuntos, donde el lenguaje complemento contiene todas las cadenas del lenguaje universal $\Sigma^*$, que no estan en $A$.
El inverso de un lenguaje se denota como $A^I$ y su efecto sobre el lenguaje es que todas las cadenas del lenguaje se invierten, esto es, si $A$ es un lenguaje, su inverso es $A^I=\{x^I\mid x\in A\}$.

Ejemplo: Si $A=\{hola,raro\}$, entonces $A^I=\{aloh,orar\}$.
El inverso de un lenguaje se anula a sí mismo. Al igual que con las cadenas, el inverso del inverso de un lenguaje, deja el lenguaje original intacto, esto es, $(A^I)^I=A$.

El uso de el inverso de un lenguaje es bueno para casí todas las operaciones sobre lenguajes, pero en el caso de la concatenación, no solo invierte las palabras concatenadas de los lenguajes, sino que también cambia el ordan de la concatenación de los lenguajes, $(A\cdot B)^I=B^IA^I$.