Automatas

¿Qué es un Autómata a Pila (PDA)?

Definición Informal

El autómata a pila es una extensión del AFN con e-transiciones, con el cual se pueden definir lenguajes regulares. Es fundamentalmente un AFN-e con la adición de una pila, en la cual se puede almacenar una cadena de símbolos y leerlos, pero únicamente se puede extraer el elemento superior.

A diferencia de un autómata finito, la presencia de la pila significa que esta nos puede recordar una cantidad infinita de información, a excepción de que el autómata a pila solo puede acceder a su información de acuerdo al modo en que se manipula, LIFO (Last-in-first-out way, primero en entrar, último en salir).

Definición Formal

La notación formal de un autómata a pila incluye siete componentes:

P=(Q,Σ,Γ,δ,Q_0,Z_0,F)

Dónde:

Q: Un conjunto finito de estados, como los estados de un autómata finito.

Σ: Un conjunto finito de símbolos de entrada, también análogo al componente correspondiente de un autómata finito.

Γ: Un alfabeto de pila finito. Este componente, que no tiene análogo en los autómatas finitos, es el conjunto de símbolos que pueden introducirse en la pila.

δ: La función de transición. Como en el autómata finito, δ controla el comportamiento del autómata. Formalmente, δ toma como argumento δ(q,a,X), donde:

1. q es un estado de Q.

2. a es cualquier símbolo de entrada de Σ o a=ε, la cadena vacía, que se supone que no es un símbolo de entrada.

3. X es un símbolo de la pila, es decir, pertenece a Γ.

La salida de δ es un conjunto finito de pares (p, γ), donde p es el nuevo estado y γ es la cadena de símbolos de la pila que reemplaza X en la parte superior de la pila. Por ejemplo, si γ = ε, entonces se extrae un elemento de la pila, si γ =X, entonces la pila no cambia y si γ =Y Z, entonces X se reemplaza por Z e Y se introduce en la pila.

Q_0: El estado inicial. El autómata a pila se encuentra en este estado antes de realizar ninguna transición.

Z_0: El símbolo inicial. Inicialmente, la pila del autómata a pila consta de una instancia de este símbolo y de nada más.

F: El conjunto de estados de aceptación o estados finales.

El autómata a pila puede observar el símbolo colocado en la parte superior de la pila y llevar a cabo su transición basándose en el estado actual, el símbolo de entrada y el símbolo que hay en la parte superior de la pila.

En una transición, el autómata a pila:

Consume de la entrada el símbolo que utiliza en la transición.

Pasa a un nuevo estado, que puede o no ser el mismo.

Reemplaza el símbolo de la parte superior de la pila por cualquier cadena.

Descripciones instantáneas (ID´s).

Intuitivamente, el autómata a pila pasa de una configuración a otra, en respuesta a los símbolos de entada, pero a diferencia del autómata finito, la configuración de autómata a pila incluye tanto el estado como el conjunto de la pila.

Dado un PDA, podemos describir un proceso de aceptación o rechazo de una cadena o gramática mediante una serie de descripciones instantáneas que definen respectivamente el estado del AP, la entrada que queda por leer, y el contenido de la pila en un momento dado.

¿Cómo se conforma un ID?

Un ID es una tripleta que está conformada por:

(q,w,γ)

Dónde:

Q; es un estado interno.

W: Es lo que falta de la entrada.

γ: Es el contenido del stack.

...