Unidad 51 Aut2matas con Pila

Apuntes

Unidad 5: Autómatas con Pila G IRÓ , V ÁZQUEZ , M ELONI , C ONSTABLE 1 Introducción El Autómata con Pila ( AP ), en inglés Push Down Automata , es básicamente un autómata finito al que se le ha incorporado una memoria de pila. La memoria de pila o memoria LIFO ( Last In First Out ) incrementa la capacidad de resolver problemas del autómata finito convencional, al incorporarle la posibilidad de memorizar total o parcialmente la cadena leída y cualquier otra marca que ayude al procesamiento de la misma. Así, el AP dispone de registros de memoria que puede usar ventajosamente, aun a p esar de las limitaciones propias de las memorias LIFO . Como ya fue anticipado en el Capítulo 1, los autómatas con pila son capaces de reconocer lenguajes generados por gramáticas menos restringidas que las regulares: las gramáticas independientes de contex to o tipo 2. El hecho de que todos los lenguajes de computación respondan a este tipo de gramáticas hace que los AP sean muy estudiados y estén ampliamente difundidos como elementos centrales en los compiladores y en otras numerosas aplicaciones. Una varia nte muy interesante del autómata con pila convencional es el...