Automatas De Pila

Autómatas de pila

Estos autómatas finitos cuentan con un dispositivo de memoria muy elemental, del tipo pila, el cual es un almacenamiento línea que funciona bajo el principio PEUS (primero en entrar, último 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 el de la forma:

t: QxT xV ->QxV*, donde la relación f(q,a,v) : (p,v) se interpreta como sigue;

Si el autómata 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 V”. Un autómata de pila reconoce a una palabra si, tras haber leído, termina con su pila vacía.

Son una extensión de los AFD a los que se les añade una memoria (pila)

Se almacenan símbolos de la cadena de entrada y de la gramática, así como caracteres especiales (#) para indicar el estado de pila vacía.

Gráficamente

Ejemplo

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

1.- O es una cadena equilibrada de paréntesis (CEP)

2.- Si σ es una CEP entonces (σ) es una CEP.

3.- La concatenación de dos CEP´s es una CEP

Para describir a un autómata que reconozca CEP´s, representamos 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 la sig.:

Y cuya función de transición actúa como sigue:

El autómata de pila reconoce al lenguaje CEP.

Webgrafía:

Delta.cs.cinvestav.mx/*gmorales/ta/node14.html

www.uhu.es/francisco.moreno/talf/docs/tema7.pdf

...