Automata

-------------------------------------------------
Autómata con pila

Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe unacadena constituida por símbolos de un alfabeto y determina si 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 decontexto en la clasificación de la Jerarquía de Chomsky.

Formalmente, un autómata con pila puede ser descrito como una séptupla  donde:
* Σ y  son alfabetos de entrada, de la cadena y de la pila respectivamente;
* S un conjunto de estados;
*
*  es el estado inicial;
*  es el símbolo inicial de la pila;
*  es un conjunto de estados de aceptación o finales.

Lainterpretación de  con  es la siguiente:
Cuando el estado del autómata es , el símbolo que la cabeza lectora está inspeccionando en ese momento es , y en la cima de la pila nos encontramos el símbolo , se realizan las siguientes acciones:
* Si , es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
* Se elimina el símbolo Z de la pila delautómata.
* Se selecciona un par  de entre los existentes en la definición de , la función de transición del autómata.
* Se apila la cadena  en la pila del autómata, quedando el símbolo  en la cima de la pila.
* Se cambia el control del autómata al estado .

[editar]Funcionamiento
Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se puedenutilizar 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 entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman deaceptació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). Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de lapila. 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.1
[editar]Representación
Una maquina de este tipo se representa de la siguiente forma

Al igual que un autómata finito un autómata de pila cuenta con un flujo de entrada y un flujo de control que puede encontrarse en unode entre un número finito de estados. Uno de estos estados se designa como el inicial y por lo menos un estado es de aceptación.
La principal diferencia es que los autómatas de pila cuentan con una pila en donde pueden almacenar información para recuperarla mas tarde.
Los símbolos que pueden almacenarse en esta pila se conocen como símbolos de pila de la maquina, constituyen un conjunto finitoque puede incluir algunos símbolos definiendo el alfabeto de la maquina y quizá algunos símbolos adicionales que se utilizan como marcas internas. Si una maquina inserta un símbolo especial en la pila antes de efectuar algún otro calculo, entonces ese símbolo en la cima de la pila puede usarse como indicador de pila vacía para cálculos posteriores, dicho símbolo es #.2
[editar]Ejemplo
Sea elsiguiente LLC ; formado por las cadenas 
Dicho lenguaje puede ser reconocido por el siguiente autómata con pila:

donde las transiciones son:

 para cualquier 
El significado de las transiciones puede ser explicado analizando la primera transición:

donde  es el estado actual,  es el símbolo en la entrada y  se extrae de la cima de la pila. Entonces, el estado del automata cambia a  y el...