Automata de Pila



Autómatas de Pila
[Escribir el subtítulo del documento]


12/04/2013
Lluvia Esmeralda Nava Jimenez

















Introducción.
Estos autómatas finitos cuentan con un dispositivo de memoria muy elemental, del tipo pila, el cual es un almacenamiento lineal que funciona bajo el principio PEUS: Primero en Entrar, Último en Salir. Sea Q un conjunto de estados,sea T el alfabeto de entrada y sea V un alfabeto de pila. La función de transición es de la forma, donde la relación  se interpreta como sigue: ``Si se está en el estado q, arriba el símbolo a y en el tope de la pila está el símbolo b entonces se pasa al estado p y se empila la palabra ''. Un autómata de pila reconoce a una palabra si, tras haberla leído, termina con su pila vacía. Autómata de Pila.
Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entreun número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO).
Lastransiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.
Un autómata a pila se encuentra en cada momento en un estado determinado y el estado siguientedepende de los tres elementos siguientes:
• estado actual
• Símbolo de entrada
• Símbolo superior de la pila
Generalmente, el autómata a pila es no determinista en el sentido de que se permite que haya varias acciones posibles en cada momento.
Un autómata de pila es una séptupla M=(Q,Σ,∆,q0,δ,F) donde:
Q= conjunto finito de estados
Σ= alfabeto de entrada
∆= alfabeto de pila
q0 ∈Q estadoinicial
F⊆Q, F≠∅, conjunto de estados finales
δ es la función de transición, definida de la siguiente forma
Q ( ) {λ} ( {λ}) P(Q *)δ × Σ∪ × ∆∪ ⎯⎯→ ×∆
es decir la forma genérica de la imagen de una terna será
δ( ) q,a,Z = {(r1,ω1),L,(rk, ωk);ri ∈Q, ωi ∈∆*}
Según esta definición un AP es en general no determinista.
Una transición es una orden que permite, en el caso de que el autómata seencontrara en estado q, en la cinta de entrada estuviera leyendo el símbolo a y el símbolo de la cima de la pila fuera Z, transitar a cualquiera de los estados ri y, extrayendo el símbolo Z de la pila, sustituirlo por la correspondiente palabra ωi. Para visualizar un autómata de pila podemos imaginar los estados y la cinta de entrada como en los autómatas finitos, pero ahora está la pila que podemosimaginar como una cinta interna (que siempre representamos como una columna) donde se van insertando o extrayendo los símbolos de pila según lo vayan mandando las transiciones.
La pila hace el papel de una memoria rudimentaria: sobre ella se escriben palabras y se van extrayendo símbolo a símbolo. Debe quedar claro el modo en que entendemos que se insertan las palabras en la pila: Si ω = a1….ak esuna palabra de longitud k y queremos insertarla en la pila de un AP, entendemos que el símbolo que queda en la cima de la pila es a1. Volveremos sobre ello más adelante.
Lo que no debemos ahora es tratar de visualizar una transición no determinista porque cada posibilidad lleva aparejado un estado diferente de la pila y se complica mucho la notación si en cada instante representamos todas las...