Siguiente: Autómatas bidireccionales Un nivel arriba: Gráficas de transición Anterior: Nociones básicas

Supresión de transiciones vacías

Sea también $T_{\mbox{\scriptsize\it GT}}(\sigma)=\mbox{\it tran\/}_{\mbox{\scriptsize\it GT}}^*(q_0,\sigma)$ el conjunto de estados accesibles en la gráfica de transición mediante $\sigma$ partiendo del estado inicial. Una palabra $\sigma \in \mbox{\it Ent\/}^*$ es reconocida por la gráfica de transición $\mbox{\it GT\/}$ si para alguna palabra $\sigma_1\in\mbox{\it Ent\/}_{\lambda}^*$ tal que $\sigma=\pi(\sigma_1)$, se tiene que $\sigma_1$ es reconocida por el autómata no-determinista $\mbox{\it AFND\/}$. El lenguaje de la gráfica está formado por todas las palabras que reconoce.

Observación 4.1   Las siguientes dos relaciones se cumplen:

• $L(\mbox{\it GT\/})=\pi(L(\mbox{\it AFND\/}))$.
• $\forall \sigma\in\mbox{\it Ent\/}^*:\sigma\in L(\mbox{\it GT\/})\Leftrightarrow T_{\mbox{\scriptsize\it GT}}(\sigma)\cap F\not=\emptyset$.

Un lenguaje $L\subset\mbox{\it Ent\/}^*$ se dice regular-G si existe una gráfica de transición $\mbox{\it GT\/}$ sobre el alfabeto $\mbox{\it Ent\/}$ tal que $L=L(\mbox{\it GT\/})$. Todo autómata no-determinista sin transiciones-$\lambda$ es una gráfica de transición. Por tanto, todo lenguaje regular-N es también regular-G. En cuanto al recíproco, se puede ver inmediatamente que todo lenguaje regular-G en el diccionario $\mbox{\it Ent\/}^*$ es regular-N en el diccionario $\mbox{\it Ent\/}_{\lambda}^*$ y, debido al lema 3.3.2, es de hecho regular en ese mismo diccionario. Así pues, toda gráfica de transición es equivalente a un autómata finito con transiciones-$\lambda$. Sin embargo, con esta construcción se ha aumentado un símbolo al alfabeto. Veamos que se puede eliminar de manera equivalente a las transiciones-$\lambda$.

Lema 4.1 (Equivalencia de GT's y AF's)   Todo lenguaje regular-G es regular. Es decir, para cada gráfica de transición $\mbox{\it GT\/}$ sobre el alfabeto $\mbox{\it Ent\/}$ existe un autómata finito $\mbox{\it AF\/}$ sobre el alfabeto $\mbox{\it Ent\/}$ tal que $L(\mbox{\it GT\/})=L(\mbox{\it AF\/})$.

En efecto, para construir un autómata finito equivalente a una gráfica de transición dada, se puede seguir cualquiera de las dos construcciones presentadas en el lema 3.3.2 partiendo del correspondiente autómata no-determinista, sólo que en vez de considerar las relaciones $\mbox{\it tran\/}_{\mbox{\scriptsize\it AFND}}^*(q,\sigma)$ se considerará las relaciones $\mbox{\it tran\/}_{\mbox{\scriptsize\it GT}}^*(q,\sigma)$. También, para evitar considerar estados irrelevantes se puede ``filtrar'' la segunda construcción con el algoritmo (3.5) de cálculo de partes accesibles. Presentamos un seudocódigo de este procedimiento en la figura (3.7). 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$. El nuevo estado final es la mónada que consiste del estado inicial q₀, $q_{01}=10\cdots 0=\mbox{\bf q}_0$.

  

Figure 3.7: Conversión de una gráfica de transición a un autómata finito equivalente.

Los estados finales serán todos aquellos nuevos estados que incluyan alguno final de los viejos estados.


Ejemplo. Sea $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ la gráfica de transición definida como sigue:

estados:

$Q=\{0,1,2,3\}$,

entradas:

$\mbox{\it Ent\/}=\{0,1\}$,

estado inicial:

q₀=0,

estados finales:

$F=\{0\}$,

transición:

$\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\}$.

La palabra $\lambda\lambda1001\lambda$ realiza la transición 01221330 y consecuentemente la palabra 1001 es reconocida. Una palabra que consista sólo de 1's no puede ser reconocida. Se puede ver que ``partir del estado 0'' es como si se ``partiera del estado 1 o del estado 2'' pues a ambos se llega desde el estado 0 con palabras de la forma $\lambda^*$. Por la misma razón, si se arriba al estado 0 se arriba también a los estados 1 y 2, si se arriba al estado 1 se arriba también al estado 2 y si se arriba al estado 3 se arriba también a los estados 0, 1, 2. Al aplicar el algoritmo (3.7) obtenemos la tabla siguiente:

$$\begin{array}{\vert\vert c\vert cc\vert\vert}\hline\hline \m... ...10 \\ \hline 0100 & 1111 & 0100 \\ \hline \hline \end{array}$$

El estado inicial del autómata equivalente consiste de la mónada formada por el estado 0, es pues 1000, y los estados finales son los que tienen prendido el ``bit'' de la extrema izquierda, a saber 1000 y 1111.
Siguiente: Autómatas bidireccionales Un nivel arriba: Gráficas de transición Anterior: Nociones básicas