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:

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

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

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

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

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

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.