next up previous contents
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{displaymath}\begin{array}{rclcl}
&& \mbox{\it tran\/}^*(q,\mbox{\it nil\...
...tran\/}^*(q,\sigma):(p,e,o)\in \mbox{\it tran\/}\}
\end{array}\end{displaymath}

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{displaymath}\begin{array}{\vert\vert l\vert l\vert\vert}\hline \hline
\...
...hline
100011 & \{q_1,q_2,q_4\} \\ \hline \hline
\end{array}\end{displaymath}

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.

 
next up previous contents
Siguiente: Representación de transiciones mediante Un nivel arriba: Autómatas no-deterministas Anterior: Autómatas no-deterministas
Guillermo Morales-Luna
2000-06-27