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{array}{lrcl} \mbox{\rm intersecci\'on: } & L_1\cap L_2... ...sigma\in\mbox{\it Ent\/}^*\vert\sigma\not\in L_1\} \end{array}$$

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 L₁ y a L₂.

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 L₁+ L₂ 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 q₀ con correspondientes transiciones-$\lambda$ $(q_0\ \lambda\ q_{01})$ y $(q_0\ \lambda\ q_{02})$. Esta gráfica reconoce a L₁+ L₂ y por tanto éste es regular-G. Como todo regular-G es también regular, L₁+ L₂ 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 q₀ 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 q₀₂ 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 q₀ 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 q₀: $(q_1\ \lambda\ q_{0})$, $q_1\in F_1$. Declaremos también como final a q₀. Esta gráfica reconoce a L₁^* y por tanto éste es regular-G. Así pues, L₁^* 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-F₁. Evidentemente, $\mbox{\it AF\/}$ reconoce a L₁^c y por tanto éste es un lenguaje regular.

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