Siguiente: Representación de transiciones mediante Un nivel arriba: Autómatas no-deterministas Anterior: Autómatas no-deterministas

Nociones básicas

Los autómatas no-deterministas se conforman como los autómatas finitos ya vistos, salvo que sus transiciones, en lugar de ser funciones, son relaciones que a cada pareja (estado,estímulo) le asocian varios, uno o ningún estado. Más precisamente: Un semiautómata no-determinista es una estructura de la forma $\mbox{\it SAFND\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$ donde

$$\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\i... ...on},} \\ q_0\in Q &:& \mbox{\rm es el estado {\em inicial}.} \end{eqnarray*}$$

Un autómata no-determinista es una pareja $\mbox{\it AFND\/}=(\mbox{\it SAFND\/},F)$ donde SAFND es un semiautómata no-determinista y $F\subset Q$ es un conjunto de estados finales. Si $(q,e,p)\in\mbox{\it tran\/}$ decimos que se puede transitar a p desde el estado q cuando arriba un símbolo e. Para cada pareja $(q,e)\in Q\times \mbox{\it Ent\/}$ su imagen bajo la transición es el conjunto $\mbox{\it tran\/}(q,e)=\{p\in Q\vert(q,e,p)\in \mbox{\it tran\/}\}$, es decir, es el conjunto de estados a los que se puede transitar desde q con e. De manera reiterada, para $(q,\sigma)\in Q\times \mbox{\it Ent\/}^*$, definimos la imagen $\mbox{\it tran\/}^*(q,\sigma)$ como sigue:

$$\begin{array}{rclcl} && \mbox{\it tran\/}^*(q,\mbox{\it nil\... ...tran\/}^*(q,\sigma):(p,e,o)\in \mbox{\it tran\/}\} \end{array}$$

Para cada $\sigma \in \mbox{\it Ent\/}^*$ definimos $T(\sigma)=\mbox{\it tran\/}^*(q_0,\sigma)$. Una palabra $\sigma \in \mbox{\it Ent\/}^*$ es reconocida por el autómata $\mbox{\it AFND\/}$ si algún estado en $T(\sigma)$ es final. El lenguaje del autómata $\mbox{\it AFND\/}$ consiste de todas las palabras que reconoce, $L(\mbox{\it AFND\/})=\{\sigma\in \mbox{\it Ent\/}^*\vert T(\sigma)\cap F\not=\emptyset\}.$


Ejemplo. Sea $\mbox{\it AFND\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ el autómata no-determinista tal que

$$\begin{eqnarray*}Q &=& \{q_0,q_1,q_2,q_3,q_4\} \\ \mbox{\it Ent\/} &=& \{0,1\}... ...ht\} \\ q_0 &:& \mbox{\rm estado inicial,} \\ F &=& \{q_4\} \end{eqnarray*}$$

En la siguiente tabla presentamos el cálculo de la correspondiente función T en algunas palabras:

$$\begin{array}{\vert\vert l\vert l\vert\vert}\hline \hline \... ...hline 100011 & \{q_1,q_2,q_4\} \\ \hline \hline \end{array}$$

Así pues, $T(100011)\cap F=\{q_4\}$ y consecuentemente $100011\in L(\mbox{\it AFND\/})$.

Observación 3.1   Todo autómata finito (determinista) es también un autómata finito no-determinista.

En efecto, las funciones son casos particulares de relaciones. Por tanto, toda función de transición, es una relación de transición.

Siguiente: Representación de transiciones mediante Un nivel arriba: Autómatas no-deterministas Anterior: Autómatas no-deterministas