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

...