Un autómata de pila o Push-Down es un autómata que cuenta con un mecanismo que permita almacenamiento ilimitado y opera como una pila. El autómata de pila (se abrevia PDA de sus siglas en inglés Push-Down Autómata) tiene una cinta de entrada, un control finito y una pila. La pila es una cadena de símbolos de algún alfabeto. El símbolo que se encuentra más a la izquierda se considera como que está en la “cima”. El dispositivo será no determinístico y tendrá un número finito de alternativas de movimiento en cada situación como se muestra en la siguiente figura un autómata de pila.
Los movimientos serán de dos tipos. En el primer tipo de movimiento se utiliza un símbolo de entrada. Dependiendo del símbolo de entrada, del símbolo de la cima y el estado de control finito, es posible un número de alternativas. Cada alternativa consiste en un estado posterior para el control finito y una cadena (posiblemente vacía) de símbolos, para sustituir al símbolo que se encuentra en la cima de la pila. Después de seleccionar una alternativa, la cabeza de entrada avanza un símbolo como se ilustra en la siguiente figura: 
La figura anterior muestra el avance de un símbolo de entrada (q1, c, B), a un estado posterior y sustitución de la cima de la pila {(q2, B)}.
El segundo tipo de movimiento conocido como movimiento ε es parecido al primero, excepto que el símbolo de entrada no se utiliza y la cabeza de la entrada no avanza después del movimiento. Este tipo de movimiento permite al PDA manipular la pila sin leer símbolos de entrada como se muestra en la figura:Manipulación de la pila sin leer símbolo de entrada. Existen dos modos de aceptar un lenguaje por un autómata de apilamiento. El primero consiste en definir el lenguaje aceptado como el conjunto de todas las entradas para las cuales una sucesión de movimientos ocasiona que el autómata de pila vacíe su pila.
La segunda manera es designando algunos estados como estados finales y definimos el lenguaje aceptado como el conjunto de todas las entradas para las cuales alguna selección de movimiento ocasiona que el autómata de pila accede un estado final.
Consideremos el siguiente ejemplo de autómata de pila definido por:
Obsérvese que no hay transiciones para todas las ternas posibles de estado, símbolo de entrada y símbolo de pila. Por lo tanto, si el PDA pasa a un estado para el cual no se especifica un estado siguiente y una acción de la pila para los símbolos actuales de la pila y la entrada, el PDA no puede volver a realizar ningún movimiento.
En particular, cuando el autómata está en el estado q4, que es el estado de aceptación, no hay ninguna transición sea cual sea el símbolo de la cima y de la entrada. Si el PDA se mueve al estado q2, entonces obsérvese que cada vez que a aparece en la entrada se apila una B en la pila.
El PDA permanece en el estado q2 hasta que se encuentra la primera b y entonces se mueve al estado q3, ninguna b puede preceder a una a.
Finalmente, en el estado q3 sólo se consideran las b’s y, cuando se encuentra cualquier b, se desapila B de la pila. (Sólo pueden desapilarse las B’s que fueron apiladas, debido a encontrarse una a en la entrada). Las únicas cadenas que acepta el PDA pertenecen al lenguaje
puesto que son las únicas cadenas de entrada que, una vez que han sido consumidas, causan que el PDA termine en el estado final q4.
MOVIMIENTO INDEPENDIENTE DE LA ENTRADA
No se tiene en cuenta el símbolo corriente en la entrada.
Interpretación: igual a la anterior, excepto que no miramos el símbolo de la entrada para tomar una decisión.
¿Qué pasa cuando γ = λ? - En este caso se reemplaza el tope de la pila por la cadena de longitud nula, es decir se realiza la operación pop sobre la pila. Esto vale para cualquier tipo de movimiento.
EJEMPLO:
Los movimientos serán de dos tipos. En el primer tipo de movimiento se utiliza un símbolo de entrada. Dependiendo del símbolo de entrada, del símbolo de la cima y el estado de control finito, es posible un número de alternativas. Cada alternativa consiste en un estado posterior para el control finito y una cadena (posiblemente vacía) de símbolos, para sustituir al símbolo que se encuentra en la cima de la pila. Después de seleccionar una alternativa, la cabeza de entrada avanza un símbolo como se ilustra en la siguiente figura: 
La figura anterior muestra el avance de un símbolo de entrada (q1, c, B), a un estado posterior y sustitución de la cima de la pila {(q2, B)}.
El segundo tipo de movimiento conocido como movimiento ε es parecido al primero, excepto que el símbolo de entrada no se utiliza y la cabeza de la entrada no avanza después del movimiento. Este tipo de movimiento permite al PDA manipular la pila sin leer símbolos de entrada como se muestra en la figura:Manipulación de la pila sin leer símbolo de entrada. Existen dos modos de aceptar un lenguaje por un autómata de apilamiento. El primero consiste en definir el lenguaje aceptado como el conjunto de todas las entradas para las cuales una sucesión de movimientos ocasiona que el autómata de pila vacíe su pila.
La segunda manera es designando algunos estados como estados finales y definimos el lenguaje aceptado como el conjunto de todas las entradas para las cuales alguna selección de movimiento ocasiona que el autómata de pila accede un estado final.
Consideremos el siguiente ejemplo de autómata de pila definido por:
Obsérvese que no hay transiciones para todas las ternas posibles de estado, símbolo de entrada y símbolo de pila. Por lo tanto, si el PDA pasa a un estado para el cual no se especifica un estado siguiente y una acción de la pila para los símbolos actuales de la pila y la entrada, el PDA no puede volver a realizar ningún movimiento.
En particular, cuando el autómata está en el estado q4, que es el estado de aceptación, no hay ninguna transición sea cual sea el símbolo de la cima y de la entrada. Si el PDA se mueve al estado q2, entonces obsérvese que cada vez que a aparece en la entrada se apila una B en la pila.
El PDA permanece en el estado q2 hasta que se encuentra la primera b y entonces se mueve al estado q3, ninguna b puede preceder a una a.
Finalmente, en el estado q3 sólo se consideran las b’s y, cuando se encuentra cualquier b, se desapila B de la pila. (Sólo pueden desapilarse las B’s que fueron apiladas, debido a encontrarse una a en la entrada). Las únicas cadenas que acepta el PDA pertenecen al lenguaje
puesto que son las únicas cadenas de entrada que, una vez que han sido consumidas, causan que el PDA termine en el estado final q4.
CARACTERÍSTICAS DEL APD:
*Cinta de entrada de sólo lectura.
*Pila, acepta lectura y escritura (pop y push).
*Cabeza lectora, se mueve a derecha (movimiento implícito).
MOVIMIENTOS QUE UN APD PUEDE REALIZAR.
Movimiento Dependiente de la entrada
Tiene en cuenta el símbolo corriente en la cinta de entrada. Luego, una transición de este tipo tendría la siguiente forma:
MOVIMIENTO INDEPENDIENTE DE LA ENTRADA
No se tiene en cuenta el símbolo corriente en la entrada.
Interpretación: igual a la anterior, excepto que no miramos el símbolo de la entrada para tomar una decisión.
¿Qué pasa cuando γ = λ? - En este caso se reemplaza el tope de la pila por la cadena de longitud nula, es decir se realiza la operación pop sobre la pila. Esto vale para cualquier tipo de movimiento.
EJEMPLO:
FUENTES DE INFORMACIÓN:
http://www.monografias.com/trabajos16/automatas-y-gramaticas/automatas-y-gramaticas.shtml#automatasdepila
http://es.scribd.com/doc/52381938/push-down
REALIZADO POR LAS ALUMNAS:
SANTIAGO CRUZ ROSA ELVIA
CARLOS DE LA CRUZ LORENA LIZETH
MENDOZA HERNÁNDEZ DAYSI
No hay comentarios:
Publicar un comentario