Siguiente: Expresiones regulares y sistemas Un nivel arriba: Expresiones regulares Anterior: Matrices de expresiones regulares

El teorema de Kleene

Veremos en esta sección que se cumple el recíproco de la proposición 4.2.3: Todo lenguaje regular ha de ser formalmente regular. Sea $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ una gráfica de transición. Consideremos la siguiente transformación:

$$\begin{eqnarray*}\Gamma: \mbox{\it Ent\/}^* &\rightarrow& {\cal P}\left(\mbox{\i... ...tau\in\mbox{\it Ent\/}^*\vert\sigma\tau\in L(\mbox{\it GT\/})\} \end{eqnarray*}$$

Observación 4.1   El lenguaje de la gráfica de transición $L(\mbox{\it GT\/})$ coincide con el conjunto $\Gamma(\mbox{\it nil\/})$.

Observación 4.2   $\forall \sigma\in\mbox{\it Ent\/}^*$:

1.

$\mbox{\it nil\/}\in\Gamma(\sigma)\ \Leftrightarrow\ \sigma\in L(\mbox{\it GT\/})$.

2.

$\forall t\in\mbox{\it Ent\/},\forall \tau\in\mbox{\it Ent\/}^*:\ t\tau\in\Gamma(\sigma)\ \Leftrightarrow\ \tau\in\Gamma(\sigma t)$.

Por tanto, se tiene la igualdad conjuntista

$$\Gamma(\sigma)=\left(\bigcup_{t\in\mbox{\scriptsize\it Ent}} t\cdot \Gamma(\sigma t)\right)\cup \gamma(\sigma),$$

donde $\gamma(\sigma)=\left\{\begin{array}{ll} \{\mbox{\it nil\/}\} &\mbox{\rm si $\s... ...tyset &\mbox{\rm si $\sigma\not\in L(\mbox{\it GT\/})$ . } \end{array}\right.$. Y puesta la igualdad anterior como una expresión regular queda

$$\Gamma(\sigma)=\sum_{t\in\mbox{\scriptsize\it Ent}} t\cdot \Gamma(\sigma t)+ \gamma(\sigma).$$ (39)

Ahora, de manera similar a como se hizo en la ec. (3.6), definimos la relación de indistinguibilidad entre los estados de GT haciendo

$$\forall p,q\in Q:\ p\equiv_{\mbox{\scriptsize\it Ind}}q\ \Lef... ...arrow \mbox{\it tran\/}^*(q,\tau)\cap F\not=\emptyset\right]$$ (40)

y de hecho la extendemos al conjunto de subconjuntos de estados, ${\cal P}(Q)$, haciendo

$$\forall P',Q'\subset Q:\ P'\equiv_{\mbox{\scriptsize\it Ind}}... ...\exists p\in P',q\in Q':p\equiv_{\mbox{\scriptsize\it Ind}}q$$ (41)

Y, también a como se hizo en el caso de los autómatas finitos, se tiene inducida una relación de indistinguibilidad en el diccionario de entrada:

$$\forall \sigma_1,\sigma_2\in\mbox{\it Ent\/}^*:\ \sigma_1\equ... ...{\scriptsize\it Ind}} T_{\mbox{\scriptsize\it GT}}(\sigma_2)$$ (42)

donde $\forall \sigma: T_{\mbox{\scriptsize\it GT}}(\sigma)=\mbox{\it tran\/}_{\mbox{\scriptsize\it GT}}^*(q_0,\sigma)$.

Observación 4.3   $\forall \sigma_1,\sigma_2\in\mbox{\it Ent\/}^*$ se cumplen las relaciones siguientes:

1.

$\forall \tau\in\mbox{\it Ent\/}^*:\tau\in\Gamma(\sigma_1)\cap\Gamma(\sigma_2)\ ... ...tarrow\ \sigma_1\tau\in L(\mbox{\it GT\/})\&\sigma_2\tau\in L(\mbox{\it GT\/}).$

2.

$\sigma_1\equiv_{\mbox{\scriptsize\it Ind,GT}}\sigma_2\Leftrightarrow \Gamma(\sigma_1)=\Gamma(\sigma_2).$

Observación 4.4   Las aseveraciones siguientes dan una alternativa para construir autómatas mínimos.

1.

La relación ``kernel de $\Gamma$'' en el diccionario $\mbox{\it Ent\/}^*$,

$$\sigma_1\equiv_{\Gamma}\sigma_2\Leftrightarrow \Gamma(\sigma_1)=\Gamma(\sigma_2),$$

coincide con la relación `` $\equiv_{\mbox{\scriptsize\it Ind,GT}}$'' y, consecuentemente, es un refinamiento de la relación que define al monoide del autómata.

2.

El cociente $\mbox{\it GT\/}_{\Gamma}=\left(\mbox{\it Ent\/}^*/\equiv_{\Gamma}\right)$ tiene una estructura de autómata finito al asociarle

(a)

las transiciones $(\Gamma(\sigma),t)\mapsto\Gamma(\sigma t)$, y

(b)

los estados finales $\{\Gamma(\sigma)\vert\mbox{\it nil\/}\in\Gamma(\sigma)\}$.

$\mbox{\it GT\/}_{\Gamma}$ es equivalente a la gráfica de transición dada $\mbox{\it GT\/}$. Además, si $S_{\mbox{\scriptsize\it GT}}$ es el autómata que coincide con el monoide de GT al dotar a éste de una estructura de autómata, entonces la función

$$\begin{eqnarray*}S_{\mbox{\scriptsize\it GT}} &\rightarrow& \mbox{\it GT\/}_{\Gamma} \\ {[\sigma]} &\mapsto& \Gamma(\sigma) \end{eqnarray*}$$

es un homomorfismo de autómatas.

3.

La función $Q\rightarrow\mbox{\it GT\/}_{\Gamma}$, $q\mapsto \Gamma(\sigma)$, donde $\sigma$ es tal que $q\in T_{\mbox{\scriptsize\it GT}}(\sigma)$ es también un homomorfismo de gráficas de transición.

4.

El índice de la relación $\equiv_{\Gamma}$ está acotado por el número de estados en GT.

Ahora bien, se tiene una correspondencia entre la imagen de $\Gamma$, o sea el conjunto de estados de $\mbox{\it GT\/}_{\Gamma}$, y las partes de Q que son accesibles desde el estado inicial q₀ en la gráfica. Por tanto, podemos calcular al autómata cociente $\mbox{\it GT\/}_{\Gamma}$ de manera similar a como se calcula el autómata equivalente a una gráfica de transición. En la Figura 4.1 presentamos el seudocódigo de este procedimiento. Si $Q=\{q_0,\ldots,q_{n-1}\}$ es el conjunto de estados de la gráfica, la lista $\mbox{\bf q}=i_0\cdots i_{n-1}\in\mbox{\it Dos\/}^n$ denota al subconjunto Q' tal que para todo j, $q_{i_j}\in Q'\Leftrightarrow i_j=1$.

  

Figure: Cálculo de la imagen de $\Gamma$ para una gráfica de transición dada.

Habiendo calculado $\mbox{\it GT\/}_{\Gamma}$, supongamos que

$$\mbox{\it GT\/}_{\Gamma}=\{\Gamma_1,\ldots,\Gamma_{n_{\Gamma}}\},$$

donde $\Gamma_1=\Gamma(\mbox{\it nil\/})$ corresponde a la palabra vacía. En este caso, las ecuaciones 4.28 dan un sistema de $n_{\Gamma}$ ecuaciones con $n_{\Gamma}$ ``incógnitas'' $\Gamma_0,\ldots,\Gamma_{n_{\Gamma}}$ de la forma

$$\forall i\leq n_{\Gamma}:\ \ \Gamma_i=\sum_{j=1}^{n_{\Gamma}} \sigma_{ij}\Gamma_j + b_i$$ (43)

donde $\forall i,j: \sigma_{ij}$ es la suma de símbolos que en $\mbox{\it GT\/}_{\Gamma}$ hacen transitar a $\Gamma_i$ hacia $\Gamma_j$:

$$\sigma_{ij}=\{t\in\mbox{\it Ent\/}\vert(\Gamma_i,t)\mapsto\Gamma_j\}$$

y

$$b_{i}=\left\{\begin{array}{ll} \mbox{\bf 1} &\mbox{\rm si $\... ...\ \mbox{\bf0} &\mbox{\rm en otro caso. } \end{array}\right.$$

Puesto de manera matricial, el sistema de ecuaciones 4.32 queda de la forma

$$\mbox{\boldmath $\Gamma$}=\mbox{\bf A}\mbox{\boldmath $\Gamma$}+\mbox{\bf b},$$

y por la manera en la que se construyó, la matriz $\mbox{\bf A}$ no posee la CPV, por tanto

$$\mbox{\boldmath $\Gamma$}=\mbox{\bf A}^*\mbox{\bf b}.$$

En la primera entrada de este vector, es decir, la correspondiente a $\Gamma_1$, se obtiene una expresión regular que describe al lenguaje reconocido por la gráfica de transición. En resumen, se tiene la

Proposición 4.1 (Kleene)   El lenguaje reconocido por cualquier gráfica de transición se puede expresar mediante una expresión regular. Es decir, todo lenguaje regular es formalmente regular.

Así pues, para una gráfica de transición $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ con sólo dos estados q₁ y q₂. Hagamos

$$\begin{eqnarray*}a_{ij} &=&\{e\in\mbox{\it Ent\/}\vert\mbox{\it tran\/}(q_i,e)=q... ...box{\bf0} &\mbox{\rm si $q_i\not\in F$ . } \end{array}\right. \end{eqnarray*}$$

Entonces, de la ec. (4.27) obtenemos: $L(\mbox{\it GT\/})=\left[a_{11}^* a_{12} a_{22}^* a_{21}\right]^* a_{11}^*b_1+a_{12} a_{22}^*b_2.$


Ejemplo: Sea $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ la gráfica de transición vista anteriormente, donde $Q=\{0,1,2,3\}$, $\mbox{\it Ent\/}=\{0,1\}$, q₀=0, $F=\{0\}$ y las transiciones son $\mbox{\it tran\/}=\left\{\begin{array}{ccc} (0\ \lambda\ 1) & (2\ 0 \ 1) & (2\... ...da\ 2) & (1\ 0 \ 3) & (3\ 1 \ 3) \\ (3\ \lambda\ 0) & & \end{array}\right\}$. Al aplicar el algoritmo 4.1 obtenemos la tabla siguiente:

$$\begin{array}{\vert\vert l\vert c\vert l\vert l\vert\vert}\hl... ... 101 & 0010 & 1 & \mbox{\rm No} \\ \hline \hline \end{array}$$

Por tanto,

$$\mbox{\it GT\/}_{\Gamma}=\{\Gamma(\mbox{\it nil\/}),\Gamma(0),\Gamma(1),\Gamma(10)\}=\{\Gamma_1,\Gamma_2,\Gamma_3,\Gamma_4\},$$

y se obtiene el sistema de ecuaciones

$$\begin{array}{lclclcl} \Gamma_1 &=& \Gamma(\mbox{\it nil\/})... ...0\Gamma(100)+1\Gamma(101) &=& 0\Gamma_2+1\Gamma_3 \end{array}$$

Puesto de manera matricial el anterior sistema de ecuaciones queda de la forma

$$\left[\begin{array}{c} \Gamma_1 \\ \Gamma_2 \\ \Gamma_3 \\ \... ...ox{\bf 1} \\ \mbox{\bf0} \\ \mbox{\bf0} \end{array}\right]$$

El lenguaje de la gráfica de transición quedará expresado por $\Gamma_1$ donde

$$\left[\begin{array}{c} \Gamma_1 \\ \Gamma_2 \\ \Gamma_3 \\ \... ...ox{\bf 1} \\ \mbox{\bf0} \\ \mbox{\bf0} \end{array}\right]$$

Al calcular la operación ``estrella'', se obtiene

$$\left[\begin{array}{cccc} \mbox{\bf0} & 0 & 1 & \mbox{\bf0} ... ...right)^* & 1 1^* & \left(1 1^* 0\right)^* \end{array}\right]$$

y consecuentemente, el lenguaje reconocido por la gráfica de transición es

$$\begin{eqnarray*}L(\mbox{\it GT\/}) &=& \mbox{\bf 1} +0 \left(1 + 0\right)^* + 1... ...ght)^* \\ &=& \mbox{\bf 1} +(0 + 1 0 0 )\left(1 + 0\right)^* \end{eqnarray*}$$

Así pues, para una gráfica de transición $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ con sólo dos estados q₁ y q₂. Hagamos

$$\begin{eqnarray*}a_{ij} &=&\{e\in\mbox{\it Ent\/}\vert\mbox{\it tran\/}(q_i,e)=q... ...box{\bf0} &\mbox{\rm si $q_i\not\in F$ . } \end{array}\right. \end{eqnarray*}$$

Entonces, de la ec. (4.27) obtenemos: $L(\mbox{\it GT\/})=\left[a_{11}^* a_{12} a_{22}^* a_{21}\right]^* a_{11}^*b_1+a_{12} a_{22}^*b_2.$


Ejemplo: Sea $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ la gráfica de transición vista anteriormente, donde $Q=\{0,1,2,3\}$, $\mbox{\it Ent\/}=\{0,1\}$, q₀=0, $F=\{0\}$ y las transiciones son $\mbox{\it tran\/}=\left\{\begin{array}{ccc} (0\ \lambda\ 1) & (2\ 0 \ 1) & (2\... ...da\ 2) & (1\ 0 \ 3) & (3\ 1 \ 3) \\ (3\ \lambda\ 0) & & \end{array}\right\}$. Al aplicar el algoritmo 4.1 obtenemos la tabla siguiente:

$$\begin{array}{\vert\vert l\vert c\vert l\vert l\vert\vert}\hl... ... 101 & 0010 & 1 & \mbox{\rm No} \\ \hline \hline \end{array}$$

Por tanto,

$$\mbox{\it GT\/}_{\Gamma}=\{\Gamma(\mbox{\it nil\/}),\Gamma(0),\Gamma(1),\Gamma(10)\}=\{\Gamma_1,\Gamma_2,\Gamma_3,\Gamma_4\},$$

y se obtiene el sistema de ecuaciones

$$\begin{array}{lclclcl} \Gamma_1 &=& \Gamma(\mbox{\it nil\/})... ...0\Gamma(100)+1\Gamma(101) &=& 0\Gamma_2+1\Gamma_3 \end{array}$$

Puesto de manera matricial el anterior sistema de ecuaciones queda de la forma

$$\left[\begin{array}{c} \Gamma_1 \\ \Gamma_2 \\ \Gamma_3 \\ \... ...ox{\bf 1} \\ \mbox{\bf0} \\ \mbox{\bf0} \end{array}\right]$$

El lenguaje de la gráfica de transición quedará expresado por $\Gamma_1$ donde

$$\left[\begin{array}{c} \Gamma_1 \\ \Gamma_2 \\ \Gamma_3 \\ \... ...ox{\bf 1} \\ \mbox{\bf0} \\ \mbox{\bf0} \end{array}\right]$$

Al calcular la operación ``estrella'', se obtiene

$$\left[\begin{array}{cccc} \mbox{\bf0} & 0 & 1 & \mbox{\bf0} ... ...right)^* & 1 1^* & \left(1 1^* 0\right)^* \end{array}\right]$$

y consecuentemente, el lenguaje reconocido por la gráfica de transición es

$$\begin{eqnarray*}L(\mbox{\it GT\/}) &=& \mbox{\bf 1} +0 \left(1 + 0\right)^* + 1... ...ght)^* \\ &=& \mbox{\bf 1} +(0 + 1 0 0 )\left(1 + 0\right)^* \end{eqnarray*}$$

Siguiente: Expresiones regulares y sistemas Un nivel arriba: Expresiones regulares Anterior: Matrices de expresiones regulares