next up previous contents
Siguiente: Ejercicios Un nivel arriba: Autómatas finitos y expresiones Anterior: Producto de autómatas

Propiedades de cerradura

Para dos lenguajes $L_1,L_2\subset\mbox{\it Ent\/}^*$ definimos los operadores siguientes:

\begin{displaymath}\begin{array}{lrcl}
\mbox{\rm intersecci\'on: } & L_1\cap L_2...
...sigma\in\mbox{\it Ent\/}^*\vert\sigma\not\in L_1\}
\end{array}\end{displaymath}

Proposición 7.1   La clase de lenguajes regulares es cerrada bajo cada uno de los anteriores operadores.

En efecto, veámoslo para cada operador.

Sean $\mbox{\it AF\/}_1$ y $\mbox{\it AF\/}_2$ sendos autómatas finitos que reconocen a L1 y a L2.

Intersección: Sea $\mbox{\it AF\/}$ el autómata producto de $\mbox{\it AF\/}_1$ y $\mbox{\it AF\/}_2$ dotado de los estados finales $F_{\land}$. $\mbox{\it AF\/}$ reconoce al lenguaje $L_1\cap L_2$ y por tanto éste es regular.

Suma: Sea $\mbox{\it AF\/}$ el autómata producto de $\mbox{\it AF\/}_1$ y $\mbox{\it AF\/}_2$ dotado de los estados finales $F_{\lor}$. $\mbox{\it AF\/}$ reconoce al lenguaje L1+ L2 y por tanto éste es regular.

Alternativamente, sea $\mbox{\it GT\/}$ la gráfica de transición que consiste de la estructura de $\mbox{\it AF\/}_1$ más la estructura de $\mbox{\it AF\/}_2$ más un estado inicial q0 con correspondientes transiciones-$\lambda$ $(q_0\ \lambda\ q_{01})$ y $(q_0\ \lambda\ q_{02})$. Esta gráfica reconoce a L1+ L2 y por tanto éste es regular-G. Como todo regular-G es también regular, L1+ L2 es regular.

Producto: Sea $\mbox{\it GT\/}$ la gráfica de transición que consiste de la estructura de $\mbox{\it AF\/}_1$ más la estructura de $\mbox{\it AF\/}_2$ más un estado inicial q0 con la transición-$\lambda$ $(q_0\ \lambda\ q_{01})$. Añadamos también una transición-$\lambda$ de cada estado final de $\mbox{\it AF\/}_1$ al estado inicial q02 de $\mbox{\it AF\/}_2$: $(q_1\ \lambda\ q_{02})$, $q_1\in F_1$. Esta gráfica reconoce a $L_1\cdot L_2$ y por tanto éste es regular-G. Así pues, $L_1\cdot L_2$ es regular.

Estrella: Sea $\mbox{\it GT\/}$ la gráfica de transición que consiste de la estructura de $\mbox{\it AF\/}_1$ más un estado inicial q0 con la transición-$\lambda$ $(q_0\ \lambda\ q_{01})$ y una transición-$\lambda$ de cada estado final de $\mbox{\it AF\/}_1$ a q0: $(q_1\ \lambda\ q_{0})$, $q_1\in F_1$. Declaremos también como final a q0. Esta gráfica reconoce a L1* y por tanto éste es regular-G. Así pues, L1* es regular.

Complemento: Sea $\mbox{\it AF\/}$ el autómata que tiene la misma estructura de $\mbox{\it AF\/}_1$ salvo en que un estado será final en $\mbox{\it AF\/}$ si y sólo si ese estado no lo es en $\mbox{\it AF\/}_1$, es decir, F=Q-F1. Evidentemente, $\mbox{\it AF\/}$ reconoce a L1c y por tanto éste es un lenguaje regular.


next up previous contents
Siguiente: Ejercicios Un nivel arriba: Autómatas finitos y expresiones Anterior: Producto de autómatas
Guillermo Morales-Luna
2000-06-27