next up previous contents
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

\begin{displaymath}f^{**}(L)=\bigcup_{\sigma\in L}f^*(\sigma).\end{displaymath}

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)=Ee 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\/}$, Eei 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.




Guillermo Morales-Luna
2000-06-27