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

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

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

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

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\/}^*$:

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

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.
Siguiente: Supresión de transiciones vacías Un nivel arriba: Gráficas de transición Anterior: Gráficas de transición