next up previous contents
Siguiente: Supresión de transiciones vacías Un nivel arriba: Gráficas de transición Anterior: Gráficas de transición

Nociones básicas

Sea $\mbox{\it Ent\/}$ un alfabeto finito y sea $\lambda$ un símbolo que no esté en $\mbox{\it Ent\/}$. Sea $\mbox{\it Ent\/}_{\lambda}=\{\lambda\}\cup\mbox{\it Ent\/}$ la extensión, mediante la añadidura del símbolo $\lambda$, del alfabeto dado. Naturalmente, el diccionario $\mbox{\it Ent\/}^*$ está incluido en el diccionario $\mbox{\it Ent\/}_{\lambda}^*$. Por otro lado, sea

\begin{eqnarray*}\pi: \mbox{\it Ent\/}_{\lambda} &\rightarrow& \mbox{\it Ent\/} ...
...pi(\sigma_1) &\mbox{\rm si $s=\lambda$ . }
\end{array}\right.
\end{eqnarray*}


la transformación que en cada palabra de $\mbox{\it Ent\/}_{\lambda}^*$ suprime todas las apariciones del símbolo $\lambda$. Acaso vale la pena decir aquí que $\pi$ es el homomorfismo entre diccionarios que extiende a las sustitución

\begin{displaymath}f_{\pi}:\xi \mapsto \left\{\begin{array}{ll}
\mbox{\it nil\/...
... &\mbox{\rm si $\xi\in\mbox{\it Ent\/}$. }
\end{array}\right.\end{displaymath}

Una gráfica de transición sobre el alfabeto $\mbox{\it Ent\/}$ es una estructura $\mbox{\it GT\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ que coincide con un autómata no-determinista $\mbox{\it AFND\/}=(Q,\mbox{\it Ent\/}_{\lambda},\mbox{\it tran\/},q_0,F)$ sobre el alfabeto $\mbox{\it Ent\/}_{\lambda}$. Se dice que todas las transiciones de la forma $(q,\lambda,p)$ son transiciones-$\lambda$, o transiciones-vacías. Para cualquier estado $q\in Q$ y cualquier palabra $\sigma \in \mbox{\it Ent\/}^*$ el conjunto de estados accesibles por $\sigma$ desde q en $\mbox{\it GT\/}$ es

\begin{displaymath}\mbox{\it tran\/}_{\mbox{\scriptsize\it GT}}^*(q,\sigma)=\big...
...a}\mbox{\it tran\/}_{\mbox{\scriptsize\it AFND}}^*(q,\sigma_1),\end{displaymath}

es decir, un estado es accesible si hay una sucesión de transiciones, que puede incluir transiciones-$\lambda$, correspondiente a los símbolos de $\sigma$ desde el estado q hasta ese estado. Introduzcamos también en este caso, la siguiente relación en $\mbox{\it Ent\/}^*$:

\begin{displaymath}\sigma_1 \equiv_{\mbox{\scriptsize\it GT}}\sigma_2\ \ \Leftri...
...1) = \mbox{\it tran\/}_{\mbox{\scriptsize\it GT}}^*(q,\sigma_2)\end{displaymath}

Como antes, se tiene que $\equiv_{\mbox{\scriptsize\it GT}}$ es una relación de equivalencia congruente con la concatenación. Por tanto, el cociente $S_{\mbox{\scriptsize\it GT}}=(\mbox{\it Ent\/}^*/\equiv_{\mbox{\scriptsize\it GT}})$ es un monoide, dicho de la gráfica de transición.
next up previous contents
Siguiente: Supresión de transiciones vacías Un nivel arriba: Gráficas de transición Anterior: Gráficas de transición
Guillermo Morales-Luna
2000-06-27