Autómata de Pila

Concepto, y ejemplos de autómatas de pila

1. Autómata de Pila
Sebastián Rodríguez 16-0929
Edgar Durán 16-0839

2. Objetivos
Autómata de Pila
○Definición básica
○Funcionamiento
○Diagrama de transición
●Autómata de Pila Determinista
○Reconocimiento
○Traducción
●Autómata de Pila no
Determinista
○Reconocimiento

3. Autómata De Pila

4. Definiciones
básicas

5. Autómata de Pila
Es un tipo de máquina
teórica, que recibe una
cadena constituida por
símbolos de un
alfabeto, y determina si
esa cadena pertenece al
lenguaje que el
autómata reconoce.

6. Cómo una palabra es aceptada?
Para que una palabra de entrada sea aceptada en un AP se deben cumplir todas
las condiciones siguientes:
1.La palabra de entrada se debe haber agotado (consumido totalmente).
2.El AP se debe encontrar en un estado final.
3.La pila debe estar vacía.

7. Funcionamiento

8. Funcionamiento
Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden
utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila
pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila
cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de
entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además
algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los
autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados
símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo
last-in-first-out (LIFO). Las transiciones entre los estados que ejecutan los autómatas de pila
dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena
x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un
estado final, después de leer toda la cadena x.

9. Una máquina de este tipo se representa de la siguiente forma

Al igual que un autómata finito un
autómata de pila cuenta con un
flujo de entrada y un flujo de
control que puede encontrarse en
uno de entre un número finito de
estados. Uno de estos estados se
designa como el inicial y por lo
menos un estado es de aceptación.
La principal diferencia es que los
autómatas de pila cuentan con una
pila en donde pueden almacenar
información para recuperarla más
tarde.

10. Cinta de
entrada
Cadena de entrada, es
donde se introducen
los caracteres
Cabeza de
lectura
Siempre situada en la
primera posición
Indicador
de estados
Muestra el estado en
que se encuentra el
autómata
Mecanismo
de control
Situado también en el
primer estado del
autómata
Pila
Almacén de
información del
autómata finito que
empieza en la cima

11. Diagrama de
transición

12. Ejemplo simple
Si tenemos una transición de la forma ((p, u, ?), (q, ?)) ? |, el AP hace lo
siguiente:
●Estando en el estado p, consume u de la entrada;
●Saca ? de la pila;
●Llega a un estado q;
●Mete ? en la pila

13. Ejemplo
Autómata de Pila
Funcionamiento Básico
Diagramas de transición

14. Pizarra
Gráfo y Tablas

15. Autómata de Pila
Determinista

16. Autómatas de Pila Determinista
La definición básica de un autómata con pila es de naturaleza no
determinista, pues la clase de los autómatas con pila
deterministas, a diferencia de lo que ocurría con aquellos modelos,
tiene una potencia descriptiva estrictamente menor. Para calificar
a un autómata con pila como determinístico deben darse dos
circunstancias; en primer lugar, por supuesto, que en la definición
de cada componente de la función de transición existan un único
elemento lo que da la naturaleza determinista.

17. Ejemplo
Autómata de Pila Determinista

19. Autómata de Pila no
Determinista

20. Autómatas de Pila no Deterministas
Un autómata finito con pila no determinista (AFPN) consta de los mismos
parámetros de un AFPD.

Donde la función de transición Δ es de la forma:

21. Ejemplo
Autómata de Pila no Determinista

23. Video Instructivo

25. Fuentes
bibliográficas
Autómatas de Pila
http://www.exa.unicen.edu.ar/catedras/ccomp1/Apu
nte4.pdf
https://es.wikipedia.org/wiki/Aut%C3%B3mata_con_
pila
http://users.dsic.upv.es/asignaturas/facultad/tdl/apil
a.pdf
http://ocw.uc3m.es/ingenieria-informatica/teoria-de
-automatas-y-lenguajes-formales/material-de-clase
-1/tema-6-automatas-a-pila
http://www.ia.urjc.es/grupo/docencia/automatas_itis
/apuntes/capitulo11.pdf
http://ocw.uc3m.es/ingenieria-informatica/teoria-de
-automatas-y-lenguajes-formales/material-de-clase
-1/tema-6-automatas-a-pila

26. Gracias por su atención!