Siguiente: Autómatas lineales Un nivel arriba: Autómatas Anterior: Autómatas regulares

Autómatas de pila

Estos autómatas finitos cuentan con un dispositivo de memoria muy elemental, del tipo pila, el cual es un almacenamiento lineal que funciona bajo el principio PEUS: Primero en Entrar, Ultimo en Salir. Sea Q un conjunto de estados, sea T el alfabeto de entrada y sea V un alfabeto de pila. La función de transición es de la forma $t : Q \times T \times V \rightarrow Q \times V^*$, donde la relación $t(q, a, v) = (p, \mbox{\bf v})$ se interpreta como sigue: ``Si se está en el estado q, arriba el símbolo a y en el tope de la pila está el símbolo b entonces se pasa al estado p y se empila la palabra $\mbox{\bf v}$''. Un autómata de pila reconoce a una palabra si, tras haberla leído, termina con su pila vacía.


Ejemplo: Las cadenas equilibradas de paréntesis son reconocidas por un autómata de pila determinista. Recordamos que

1.

() es una cadena equilibrada de paréntesis, (CEP).

2.

Si $\sigma$ es una CEP entonces $(\sigma)$ es una CEP.

3.

La concatenación de dos CEP's es una CEP.

Para describir a un autómata que reconozca CEP's, representemos al paréntesis que abre ``('' con el símbolo a, al paréntesis que cierra ``)'' con c, y con b al ``blanco'', es decir, al fin de la cadena de entrada. Consideremos el autómata de pila cuyas componentes son las siguientes:

$$\begin{array}{lcl} Q = \{\mbox{\rm Seguir}, \mbox{\rm Exito}... ...x{\rm Seguir} &:& \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 Seguir},a,y) &\mapsto& (\mb... ...box{\it nil\/}) &\mbox{\rm equilibrio verificado.} \end{array}$$

Es claro que este autómata de pila reconoce al lenguaje CEP.
Siguiente: Autómatas lineales Un nivel arriba: Autómatas Anterior: Autómatas regulares