alpa

Autómata a pila: es aquella máquina que reconoce lenguajes generados por gramáticas libres de contexto. Pueden ser determinista y no determinista, pero un autómata a pila no determinista no puedereducirse a otro determinista. Se define como un conjunto de 7 elementos AP= (Ʃ ; ᴦ ; Q; Z; q0; f; F)
Ʃ = alfabeto de entrada de la cadena, ᴦ = alfabeto de la Pila, Q = conjunto nito de estados,
Z= Símbolo inicial de la Pila, q0 = estado inicial, f = es una aplicación, transición, F = conjunto de estados finales o conjunto de estados de aceptación
El AP solo puede acceder a la informaciónde su pila a través de la cima de la pila
Los AP reconocen todos los lenguajes en dependientes de contexto y solo estos
La principal diferencia en relación a un AF es que los autómatas de pilacuentan con una pila donde pueden almacenar información para recuperarla más tarde.
Esquemáticamente dispone de: *una cinta de entrada: de la que lee los símbolos de la cadena. * Una memoria: conestructura de pila, el elemento que se lee es el último que se escribió en ella. * un mecanismo de control: que hace cambiar de estado a otro.
En cada momento el estado siguiente depende del estadoanterior, del símbolo de entrada que se encuentra en la cima de la pila.
Funcionamiento de un AP: * Dependiente de entrada: se lee un símbolo de la cinta y en función del símbolo leído , del estado en quese encuentre el AP en el momento de la lectura y elemento situado en la cima de la pila, pasara a otro estado * Independiente de entrada: el cambio de estado depende solo del contenido de la pila ydel estado en que se encuentre la máquina. Ni lee ni avanza la cinta.
Una cadena se acepta de dos formas distintas: *por vaciado de pila: la lectura de la cadena escrita en la cinta lleva al autómata avaciar la pila cuando acepta la palabra, - un autómata acepta un lenguaje por vaciado de pila si para cada una de las palabras después de ser leída causa que al final del proceso la pica se...