Operaciones sobre lenguajes1
Sobre lenguajes L_1,L_2\subseteq \Sigma^* podemos claramente hacer todas las operaciones que podemos hacer entre conjuntos genericos, por ejemplo L_1\cap L_2, or L_1\cup L_2, o tomar el complemento de L_1, es decir \overline{L_1}=\Sigma^*\setminus L_1.
Concatenación
Mediante el símbolo lambda mayúscula \Lambda, denotamos el lenguaje que contiene únicamente a la palabra vacía \lambda. Es decir \Lambda =\{\lambda\}\ .
Definimos ahora la concatenación de dos lenguajes, que denotaremos de forma análoga a la concatenación de dos palabras.
La concatenación de un lenguaje L_1\subseteq \Sigma^* con un lenguaje L_2\subseteq \Sigma^* da como resultado un nuevo lenguaje L_1\cdot L_2\subseteq \Sigma^* que contiene aquellas palabras que se pueden obtener concatenando una palabra cualquiera de L_1 con una palabra cualquiera de L_2. Es decir, L_1\cdot L_2 =\{w_1w_2 \mid w_1\in L_1 \land w_2\in L_2\}\ .
Ejemplo 1 \{a,bb\}\cdot\{b,ba\}=\{ab,aba,bbb,bbba\}\ . Al concatenar estos dos lenguajes finitos, obtenemos como resultado un lenguaje con tantas palabras como la multiplicación del número de palabras del primer lenguaje por el número de palabras del segundo lenguaje.
Se puede comprobar fácilmente que el lenguaje \Lambda es el elemento neutro de la concatenación de lenguajes: por todo lenguaje L \Lambda \cdot L = L \cdot \Lambda = L\ .
En cambio, el lenguaje vacío \emptyset concatenado con cualquier otro lenguaje da como resultado el lenguaje vacío: por todo lenguaje L \emptyset\cdot L = L \cdot \emptyset =\emptyset\ . Esto es porque no se puede construir ninguna palabra escogiendo una del lenguaje vacío y concatenándola con otra.
También se puede demostrar sin demasiada dificultad que la concatenación de lenguajes es una operación asociativa: por todo lenguajes L_1, L_2 y L_3 L_1(L_2L_3)=(L_1L_2)L_3\ .
Exponenciación
Una palabra w elevada a un natural n da como resultado concatenar la propia w consigo misma n veces, w^n=\underbrace{ww \cdots w}_{n}\ . Por ejemplo, w^2=ww, w^1=w, y, por convenio, w^0=\lambda, que recordemos que es el neutro de la concatenación de palabras.
Fijaos que de este modo se cumple que w^n=w\cdot w^{n-1} por todo n\geq 1.
Un lenguaje L elevado a un natural n da como resultado concatenar el propio L consigo mismo n veces: L^n=\underbrace{L\cdot L \cdots L}_{n}\ .
Por ejemplo, L^2=LL, L^1=L, y por convenio definimos que L^0=\Lambda que recordemos que es el neutro de la concatenación de lenguajes.
Fijaos que de este modo se cumple que L^n=L\cdot L^{n-1} para todo n\geq 1.
Estrella de Kleene
La estrella de Kleene un lenguaje L da como resultado un nuevo lenguaje L^* que contiene aquellas palabras que se pueden obtener a base de escoger un número finito de palabras de L y concatenarlas. Formalmente, L^* = \bigcup_{n=0}^\infty L^n = \{w\in \Sigma^* \mid \exists n\in \mathbb{N} \exists w_1,w_2,\dots, w_n\in L\ w=w_1w_2\cdots w_n\}\ .
Dicho de otro modo, una palabra w es en L^* si y sólo si podemos escoger un cierto número de palabras w_1 hasta w_n de L, concatenarlas y obtener así w.
Ejemplo 2 \{a\}^*=\{\lambda, a, aa, aaa, aaaa, \dots\}=\{a^n \mid n\in \mathbb N\}\ . Escogiendo cero palabras del lenguaje \{a\} y concatenándolas obtenemos la palabra vacía \lambda. Escogiendo una palabra obtenemos a. Escogiendo dos palabras resulta que ambas son a y por tanto obtenemos aa. Y así sucesivamente vemos que el resultado de la operación estrella en este caso es el conjunto de todas las palabras posibles que se pueden formar con a.
Ejemplo 3 \{ab\}^*=\{\lambda, ab,abab, ababab, \dots\}=\{(ab)^n \mid n\in \mathbb N\}\ . En este caso, tras aplicar la operación estrella al lenguaje \{ab\} obtenemos \lambda, ab, abab y así sucesivamente.
Ejemplo 4 Consideramos el lenguaje con la palabra a y con la palabra bb, es decir \{a,bb\}. En este caso, tras aplicar la operación estrella obtenemos \lambda, a, bb, aa, abb, bba, bbbb y así sucesivamente.
Ejemplo 5 Si aplicamos la estrella al lenguaje de las palabras de longitud par, lo volvemos a obtener a él mismo. Esto es porque si concatenamos varias palabras de longitud par obtenemos nuevamente una palabra de longitud par. Es decir \{w\in \Sigma^* \mid |w|\in \dot 2\}^*=\{w\in \Sigma^* \mid |w|\in \dot 2\}\ .
La operación más (+) se define de forma similar a la operación estrella. Ambas operaciones difieren en que el más no obliga necesariamente a incluir la palabra vacía. L^+=\bigcup_{n=1}^\infty= L^1\cup L^2\cup \cdots De hecho, L estrella siempre coincide con la unión de L más y el conjunto con la palabra vacía, L^*=L^+\cup \Lambda y \lambda \in L^+ \Leftrightarrow \lambda \in L\ .
Reverso
El reverso de una palabra w da como resultado otra palabra w^R de la misma longitud y cumpliendo que su primer símbolo es el último símbolo de w, su segundo símbolo es el penúltimo símbolo de w y así sucesivamente. Es decir, si w=s_1s_2\cdots s_{|w|}, entonces w^R=s_{|w|}\cdots s_2 s_1, donde s_1, s_2, etc denotan los simbolos de la palabra w.
Ejemplo 6 El reverso de w=aabab es w^R=(aabab)^R=babaa.
No es difícil comprobar que el reverso de la concatenación de dos palabras da como resultado el reverso de la segunda palabra concatenado con el reverso de la primera palabra. Es decir (uv)^R=v^Ru^R por toda palabras u,v.
El reverso de un lenguaje L\subseteq \Sigma^* es el conjunto de palabras que resultan de aplicar la operación reverso a todas las palabras de L. Es decir, L^R=\{w^R\in \Sigma^* \mid w\in L\}=\{w\in \Sigma^* \mid w^R\in L\}\ .
Ejemplo 7 El reverso del conjunto de palabras sobre \{a,b\} que empiezan por a da como resultado el conjunto de palabras sobre \{a,b\} que acaban en a. Es decir \{w\in \{a,b\}^* \mid \exists w'\ w= aw'\}^R=\{w\in \{a,b\}^* \mid \exists w'\ w= w'a\}\ .
No es difícil comprobar que el reverso de la concatenación de dos lenguajes da como resultado el reverso del segundo lenguaje concatenado con el reverso del primer lenguaje. Es decir (L_1L_2)^R=L_2^R L_1^R por todo lenguajes L_1 y L_2.
Morfismos
Un morfismo \sigma es una función que transforma palabras sobre un alfabeto \Sigma_1 en palabras sobre otro alfabeto \Sigma_2 pero es un tipo de función muy particular y sencillo porque adicionalmente cumple que la aplicación del morfismo conmuta con la concatenación de palabras. Es decir que la imagen de la concatenación de dos palabras coincide con la concatenación de las respectivas imágenes. En otras palabras, una función \sigma \colon \Sigma_1^* \to \Sigma_2^* es un morfismo si cumple que para cada palabras u y v, \sigma(uv)=\sigma(u)\sigma(v)\ .
De este modo la imagen con \sigma de una palabra cualquiera w=a_1a_2\dots a_n, que describimos de forma genérica como la concatenación de simbulos a_1, a_2, hasta a_n, da como resultado la imagen con \sigma de a_1 concatenado con la imagen de a_2 y así sucesivamente. Es decir, \sigma(a_1a_2\cdots a_n)=\sigma(a_1)\sigma(a_2)\cdots \sigma(a_n)\ .
No resulta difícil comprobar que la imagen de la palabra vacía \lambda por un morfismo da como resultado la palabra vacía. Es decir, por cualquier morfismo \sigma\colon \Sigma_1^* \to \Sigma_2^* \sigma(\lambda)=\lambda\ .
De hecho para definir un morfismo \sigma\colon \Sigma_1^* \to \Sigma_2^* basta con definir solamente la imagen de los símbolos del alfabeto \Sigma_1 ya que entonces la imagen de cualquier palabra se puede calcular en términos de las imágenes de los símbolos.
Ejemplo 8 Para definir un morfismo \sigma\colon \{a,b,c\}^* \to \{0,1\}^* entre las palabras sobre \{a,b,c\} y las palabras sobre \{0,1\}^* basta con definir las imágenes de a, b y c. Por ejemplo consideramos \sigma(a)=0,\quad \sigma(b)=11,\quad \text{i}\quad \sigma(c)=\lambda\ . Como consecuencia de esta definición y del hecho de que \sigma es un morfismo podemos ahora calcular la imagen de cualquier palabra sobre \{a,b,c\}. Por ejemplo la imagen de accbacb se calcula concatenando las imágenes de sus simbolos. \sigma(accbacb)=\sigma(a)\sigma(c)\sigma(c)\sigma(b)\sigma(a)\sigma(c)\sigma(b)=0\lambda \lambda 11 0 \lambda 11 = 011011\ .
Dado un morfismo \sigma\colon \Sigma_1^* \to \Sigma_2^* y un lenguaje L\subseteq \Sigma_1^*, el lenguaje imagen de L por \sigma queda definido de forma natural como el lenguaje de las palabras que son imagen de alguna palabra de L. Es decir \sigma(L)=\{\sigma(w)\in \Sigma_2^* \mid w\in L\}\ .
Similarmente para un lenguaje L\subseteq \Sigma_2^*, el lenguaje anti-imagen de L queda definido como el conjunto de palabras cuya imagen está en L. Esa decir \sigma^{-1}(L)=\{w\in \Sigma_1^* \mid \sigma(w)\in L\}\ .
No es difícil comprobar que la aplicación de un morfismo sobre lenguajes conmuta con la concatenación de lenguajes. Es decir \sigma(L_1L_2)=\sigma(L_1)\sigma(L_2) por cualquier morfismo \sigma\colon \Sigma_1^* \to \Sigma_2^* y lenguajes L_1,L_2\subseteq \Sigma_1^*.