Siguiente: Ejercicios Un nivel arriba: Propiedades de cerradura bajo Anterior: Sustituciones

Imágenes homomorfas

Un homomorfismo es un caso particular de una sustitución f en la que, para cada $e_i\in\mbox{\it Ent\/}$, E_ei es una mónada, consistente de una sola palabra. Por lo visto en la sección anterior, tenemos que si $L\subset\mbox{\it Ent\/}^*$ es regular y f es un homomorfismo entonces $f(L)\subset(\mbox{\it Ent\/}')^*$ también es regular. Ahora bien, si $K\subset(\mbox{\it Ent\/}')^*$ es un lenguaje cualquiera, su imagen inversa bajo el homorfismo f es el lenguaje

$$f^{-1}(K)=\{\sigma\in\mbox{\it Ent\/}^*\vert f(\sigma)\in K\}.$$

Es claro que se cumplen las inclusiones siguientes:

$$\begin{eqnarray*}\forall L\subset\mbox{\it Ent\/}^* &:& L\subset f^{-1}(f(L)) \\... ...forall K\subset(\mbox{\it Ent\/}')^* &:& K\supset f(f^{-1}(K)) \end{eqnarray*}$$

(si, por ejemplo, f fuese inyectiva, entonces valdrían las igualdades en las inclusiones anteriores.)

Proposición 8.2   Las imágenes inversas de lenguajes regulares, bajo homomorfismos, son regulares. En otras palabras, si $K\subset(\mbox{\it Ent\/}')^*$ es un lenguaje regular y $f:\mbox{\it Ent\/}^* \rightarrow (\mbox{\it Ent\/}')^*$ es un homomorfismo, entonces L=f^-1(K) es también un lenguaje regular.

En efecto, supongamos que $\mbox{\it AF\/}'=(Q,\mbox{\it Ent\/}',\mbox{\it tran\/}',q_0,F)$ es un autómata finito que reconoce al lenguaje K. Sea $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ el autómata finito que coincide con el anterior salvo en que $\mbox{\it tran\/}:(q,e)\mapsto \mbox{\it tran\/}'^*(q,f(e))$. Es claro que

$$\forall \sigma\in\mbox{\it Ent\/}^*: \ \sigma\in L(\mbox{\it AF\/})\Leftrightarrow f(\sigma)\in L(\mbox{\it AF\/}').$$

Así pues, $\mbox{\it AF\/}$ reconoce al lenguaje f^-1(K) y por tanto, éste es regular.



Siguiente: Ejercicios Un nivel arriba: Propiedades de cerradura bajo Anterior: Sustituciones