Siguiente: Imágenes homomorfas Un nivel arriba: Propiedades de cerradura bajo Anterior: Propiedades de cerradura bajo

Sustituciones

Sean $\mbox{\it Ent\/}$ y $\mbox{\it Ent\/}'$ dos lenguajes. Una sustitución es una función

$$\begin{eqnarray*}f:\mbox{\it Ent\/} &\rightarrow& {\cal P}(\mbox{\it Ent\/}') \\ s &\mapsto& E_s \end{eqnarray*}$$

que a cada símbolo de $\mbox{\it Ent\/}$ le asocia un lenguaje en $\mbox{\it Ent\/}'$. Naturalmente, una sustitución f se extiende a todo $\mbox{\it Ent\/}^*$ haciendo

$$\begin{eqnarray*}f^*:\mbox{\it Ent\/}^* &\rightarrow& {\cal P}(\mbox{\it Ent\/}'... ...&=& \{\mbox{\it nil\/}\} \\ f^*(\sigma e) &=& f^*(\sigma)f(e) \end{eqnarray*}$$

Ahora, si $L\subset\mbox{\it Ent\/}^*$ es un lenguaje, definimos

$$f^{**}(L)=\bigcup_{\sigma\in L}f^*(\sigma).$$

Por abuso de notación denotaremos a las funciones f^** y f^* como f simplemente.

Proposición 8.1   Si $L\subset\mbox{\it Ent\/}^*$ es un lenguaje regular y $f:\mbox{\it Ent\/} \rightarrow {\cal P}(\mbox{\it Ent\/}')$ es una sustitución, entonces f(L) es también un lenguaje regular, siempre que $\forall e\in\mbox{\it Ent\/}$, f(e)=E_e lo sea.

En efecto, basta ver que f(L) se representa mediante una expresión regular. Pero, como L es regular, existe una expresión regular $E(\mbox{\bf e})=E(e_1,\ldots,e_m)$ que lo representa. Ahora bien, para cada $e_i\in\mbox{\it Ent\/}$, E_ei es una expresión regular. Por tanto $f(L)=E\left(\left(e_i\vert E_{e_i}\right)_i\right)$ es una expresión regular.