Automatas De Pila

AUTOMATAS DE PILA

Definición:

Un autómata de pila es formalmente una séxtupla de la forma (Z,V,P,delta,0,F), donde

Z Conjunto finito de estados.

V Alfabeto de la máquina.

P Conjunto finito de símbolos de pila.

delta Colección finita de transiciones.

0 Estado inicial.

F Conjunto de estados de aceptación.

Esquemáticamente:

El autómata de pila analiza cadenas de la misma manera que los autómatas

finitos.

La diferencia con aquellos es que el símbolo leído, x , tenia en cuenta el estado de la máquina A, donde se encontraba y la función de transición ubicada en el par ordenado (A,x) nos daba el destino del nuevo estado B. Utilizando el correspondiente grafo esta transición se manifestaba como

Las transiciones en los autómatas de pila se representan en cambio

A es el estado origen donde se encuentra la máquina. Si la tira en la celda señala por la cabeza lectora tiene el símbolo al x, lee lo que tiene la pila en su cabeza si es c. Lo saca y graba en la cabeza de la pila el elemento d.

Debemos agregar que al comienzo La primera celda de la cinta se coloca sobre la cabeza lectora con la pila vacía.

Lo importante es el agregado a los autómatas finitos de un sistema de memoria interna en forma de pila con lo que se incrementa considerablemente el potencial de procesamiento de lenguaje del autómata.

Consideremos algunas características que se presentan

# es un símbolo de pila que suele usarse como elemento de control para detectar el fin de la pila.

La palabra vacía & juega de distinta manera según las tres posiciones que puede ocupar en la flecha de la transición.

En primer lugar sobre la flecha significa que no se lee nada de la tira y la misma no avanza una posición,

En segundo lugar no extraemos nada de la pila

En tercer lugar no ponemos nada en la pila.

Vamos a dar un ejemplo de un autómata a pila que justamente reconoce las palabras del lenguaje (x^n, y^n /n es N) para el cual no existe autómata finito que lo reconociera.

El estado 0 es el de inicio. El 3 es el de aceptación. Al comenzar, asumiendo que la pila se encuentra vacía,la máquina se encuentra apuntando al primer símbolo de la tira. La transición &, &, # indica que no lee nada de la tira y no avanza a la segunda celda, la segunda & señala que no se saca nada de la pila, y # en tercer lugar nos dice que colocamos este símbolo en la pila en la parte superior y que la misma por estar vacía, va a ser el único símbolo que lo ocupará. Finalmente pasa la maquina al estado 1. En este estado comenzamos a leer desde la primera celda hacia la derecha .Por cada x que se lee de la celda no sacamos nada de la pila pero si colocamos la x en la pila en cada caso, y se pasa a la derecha con la cabeza lectora. Este proceso continua hasta que se lee una y. En ese momento tenemos la pila con un símbolo # en el fondo y encima de ella tantas x como las que tenia la cinta en la primera parte. Al leerse la primera y, se extrae la x que esta en la parte superior de la pila. A continuación, en estado 2, por cada y que se lee de la tira, se retira una x de la pila, continuando con su desplazamiento a la derecha, Esto continua hasta que se terminan los símbolos de la tira. Pero como en la pila, si hubo tantas y como x, quedo el símbolo # en la cabeza de la pila. Por lo tanto de realiza la transición &, #, & con lo que no se lee nada de la tira, quedando la cabeza lectora en esa posición, se extrae el símbolo # de la pila (la pila queda vacía) y no coloca nada en la pila. Pasamos al estado 3, de aceptación, sobre el que no hay transición. De esta manera termina el proceso y como conclusión se tiene que se

...