AUTOMATAS DE PILA

AUTOMATAS DE PILA
Definición:
Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determinasi esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquíade Chomsky.
Notación grafica para los autómatas de pila:

Así:
Los símbolos del alfabeto de entrada se representan mediante las letras minúsculas próximas al principio del alfabeto, por ejemplo, a,b.
Los estados se representan mediante q y p, típicamente, u otras letras próximas en orden alfabético.
Las cadenas de símbolos de entrada se representan mediante las letras minúsculas próximas al finaldel alfabeto, por ejemplo, w o z.
Los símbolos de la pila se representan mediante las letras mayúsculas próximas al final del alfabeto, por ejemplo, X o Y.
Las cadenas de los símbolos de pila serepresentarán mediante letras griegas, por ejemplo, α o γ.

Descripciones instantáneas de un autómata de pila.
Una descripción instantánea o configuración es una terna (q, x, Z) donde q ∈ Q, x ∈ Σ*, Z ∈ Γ*que define: el estado del autómata, la entrada que resta por leer y el contenido de la pila en un momento dado.
Lenguajes de un autómata de pila
Tomemos en cuenta que un autómata a pila acepta suentrada consumiéndola e introduciendo un estado de aceptación. Este enfoque se denomina “aceptación por estado final”. Existe un segundo enfoque que permite definir el lenguaje de un autómata a pila queproporciona aplicaciones importantes. También podemos definir, para cualquier autómata a pila, el lenguaje “aceptado por pila vacía”, que es el conjunto de cadenas que hacen que el autómata a pila vacíesu pila, partiendo de la descripción ID inicial. Estos dos métodos son equivalentes, en el sentido de que un lenguaje L tiene un autómata a pila que lo acepta por estado final si y sólo si L tiene un...