next up previous contents
Siguiente: Autómatas de pila no-deterministas Un nivel arriba: Autómatas Anterior: Autómatas de pila

Autómatas lineales

Los autómatas lineales son autómatas de pila deterministas que a lo largo de su computación sólo hacen un ``cambio de turno''. A grandes rasgos, esto significa que toda computación consiste de un procedimiento de empilar consecutivamente para después pasar a desempilar.


Ejemplo: Consideremos el lenguaje de palíndromas con una marca central:

\begin{displaymath}L=\{\mbox{\bf y}M\mbox{\bf x}\vert\mbox{\bf x}\in (0+1)^*,\mbox{\bf y}=\mbox{\it reverso\/}(\mbox{\bf x})\}.\end{displaymath}

Consideremos el autómata de pila cuyas componentes son las siguientes:

\begin{displaymath}\begin{array}{lcl}
Q = \{\mbox{\rm Meter}, \mbox{\rm Sacar},...
...ox{\rm Meter} &:& \mbox{\rm s\'\i mbolo inicial},
\end{array}\end{displaymath}

y cuya función de transición actúa como sigue,

\begin{displaymath}t:\begin{array}{lcll}
(\mbox{\rm Meter},0,y) &\mapsto& (\mbo...
...},\mbox{\it nil\/}) &\mbox{\rm estado de \'exito,}
\end{array}\end{displaymath}

donde $y\in V$ y b es el símbolo ``blanco''. En cualquier otra instancia de t, ésta transitará al estado de fracaso. Es claro que este autómata de pila reconoce al lenguaje L.

Guillermo Morales-Luna
2000-06-27