Autómatas con Pila

Autómatas con Pila

Ingeniería en Sistemas

​Autómatas con Pila

​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 incrementa la capacidad de resolver problemas de 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.

​Autómatas con Pila

​Por tanto, el AP dispone de registros de memoria que puede usar ventajosamente, aun a pesar de las limitaciones propias de las memorias LIFO.

​

​Los Autómatas con Pila son capaces de reconocer los lenguajes generados por gramáticas menos restringidas que las regulares: las gramáticas independientes de contexto o tipo 2.

¿Cómo está definido el Autómata con Pila?

​Agregarle una memoria de pila a un autómata finito convencional implica incorporarle dos nuevos componentes:

1. ​El Alfabeto de símbolos de la pila

2. Un símbolo especial destinado a servir de referencia, llamado marca de fondo de pila.​

​Este último es necesario debido a la naturaleza de los accesos LIFO y con el fin de permitir comprobar si la pila ya está descargada.

¿Cómo está definido el Autómata con Pila?

Formalmente, un autómata de pila (pushdown automata) se define como una séxtupla, donde se maneja:

• ​Alfabeto de símbolos de entrada

• ​Alfabeto de símbolos de la pila

• ​Conjunto finito y no vacío de estados posibles

• ​Estado Inicial

• ​Conjunto de estados de aceptación

• ​Símbolo de referencia de la pila (#)

​

​

​¿Cómo trabaja u opera?

​Al incluir un nuevo alfabeto utilizando una memoria de pila (stack), se brinda al autómata un par de operaciones adicionales al momento de verificar si una palabra es aceptada o no:

• ​La operación push: Ingresa elementos a la pila.

• ​La operación pop: Retira elementos de la pila.

​Una palabra es aceptada por el autómata si al procesarla completamente se llega a un estado final y la pila queda vacía; y debido al no determinismo del autómata, es posible que al terminar de procesar la palabra, varios estados estén activos. Es suficiente con que uno de estos sea un estado final.

​Diagrama representativo de un AP

​Autómatas Finitos y Autómatas de Pila

​Es importante mencionar que:

• ​Todo lenguaje aceptado por un autómata finito es también aceptado por un autómata de pila.

• ​Cualquier lenguaje regular es aceptado, por tanto, por un autómata de pila.

• ​Los lenguajes libres de contexto son aceptados por los autómatas de pila y los lenguajes generados por gramáticas de tipo 2 (libres de contexto) son lenguajes libres de contexto.