b'\n_START_ARTICLE_\nAut\xc3\xb3mata con pila\n_START_PARAGRAPH_\nUn aut\xc3\xb3mata con pila, aut\xc3\xb3mata a pila o aut\xc3\xb3mata de pila es un modelo matem\xc3\xa1tico de un sistema que recibe una cadena constituida por s\xc3\xadmbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el aut\xc3\xb3mata reconoce._NEWLINE_El lenguaje que reconoce un aut\xc3\xb3mata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificaci\xc3\xb3n de la Jerarqu\xc3\xada de Chomsky.\n_START_SECTION_\nFuncionamiento\n_START_PARAGRAPH_\nLos aut\xc3\xb3matas de pila, en forma similar a como se usan los aut\xc3\xb3matas finitos, tambi\xc3\xa9n se pueden_NEWLINE_utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A._NEWLINE_Los aut\xc3\xb3matas de pila pueden aceptar lenguajes que no pueden aceptar los aut\xc3\xb3matas finitos._NEWLINE_Un aut\xc3\xb3mata de pila cuenta con una cinta de entrada y un mecanismo de control que puede_NEWLINE_encontrarse en uno de entre un n\xc3\xbamero finito de estados. Uno de estos estados se designa como_NEWLINE_estado inicial, y adem\xc3\xa1s algunos estados se llaman de aceptaci\xc3\xb3n o finales. A diferencia de los_NEWLINE_aut\xc3\xb3matas finitos, los aut\xc3\xb3matas de pila cuentan con una memoria auxiliar llamada pila. Los_NEWLINE_s\xc3\xadmbolos (llamados s\xc3\xadmbolos de pila) pueden ser insertados o extra\xc3\xaddos de la pila, de acuerdo con el_NEWLINE_manejo last-in-first-out (LIFO)._NEWLINE_Las transiciones entre los estados que ejecutan los aut\xc3\xb3matas de pila dependen de los s\xc3\xadmbolos de_NEWLINE_entrada y de los s\xc3\xadmbolos de la pila. El aut\xc3\xb3mata acepta una cadena x si la secuencia de transiciones,_NEWLINE_comenzando en estado inicial y con pila vac\xc3\xada, conduce a un estado final, despu\xc3\xa9s de leer toda la_NEWLINE_cadena x.\xe2\x80\x8b\n_START_SECTION_\nRepresentaci\xc3\xb3n\n_START_PARAGRAPH_\nUna m\xc3\xa1quina de este tipo se representa de la siguiente forma_NEWLINE_Al igual que un aut\xc3\xb3mata finito un aut\xc3\xb3mata de pila cuenta con un flujo de entrada y un flujo de control que puede encontrarse en uno de entre un n\xc3\xbamero finito de estados. Uno de estos estados se designa como el inicial y por lo menos un estado es de aceptaci\xc3\xb3n._NEWLINE_La principal diferencia es que los aut\xc3\xb3matas de pila cuentan con una pila en donde pueden almacenar informaci\xc3\xb3n para recuperarla m\xc3\xa1s tarde._NEWLINE_Los s\xc3\xadmbolos que pueden almacenarse en esta pila se conocen como s\xc3\xadmbolos de pila de la m\xc3\xa1quina, constituyen un conjunto finito que puede incluir algunos s\xc3\xadmbolos definiendo el alfabeto de la m\xc3\xa1quina y quiz\xc3\xa1 algunos s\xc3\xadmbolos adicionales que se utilizan como marcas internas. Si una m\xc3\xa1quina inserta un s\xc3\xadmbolo especial en la pila antes de efectuar alg\xc3\xban otro c\xc3\xa1lculo, entonces ese s\xc3\xadmbolo en la cima de la pila puede usarse como indicador de pila vac\xc3\xada para c\xc3\xa1lculos posteriores, dicho s\xc3\xadmbolo es #.\xe2\x80\x8b\n_START_SECTION_\nEjemplo\n_START_PARAGRAPH_\nSea el siguiente LLC ; formado por las cadenas  _NEWLINE_Dicho lenguaje puede ser reconocido por el siguiente aut\xc3\xb3mata con pila:_NEWLINE_donde las transiciones son:_NEWLINE_ para cualquier _NEWLINE_El significado de las transiciones puede ser explicado analizando la primera transici\xc3\xb3n:_NEWLINE_donde  es el estado actual,  es el s\xc3\xadmbolo en la entrada y  se extrae de la cima de la pila. Entonces, el estado del aut\xc3\xb3mata cambia a  y el s\xc3\xadmbolo  se coloca en la cima de la pila._NEWLINE_La idea del funcionamiento del aut\xc3\xb3mata es que al ir leyendo los diferentes s\xc3\xadmbolos a, estos pasan a la pila en forma de s\xc3\xadmbolos A. Al aparecer el primer s\xc3\xadmbolo b en la entrada, se comienza el proceso de desapilado, de forma que coincida el n\xc3\xbamero de s\xc3\xadmbolos b le\xc3\xaddos con el n\xc3\xbamero de s\xc3\xadmbolos A que aparecen en la pila.\n_START_SECTION_\nAut\xc3\xb3mata con pila deterministico\n_START_PARAGRAPH_\nN\xc3\xb3tese que, a diferencia de un aut\xc3\xb3mata finito o una m\xc3\xa1quina de Turing, la definici\xc3\xb3n b\xc3\xa1sica de un aut\xc3\xb3mata con pila es de naturaleza no determinista, pues la clase de los aut\xc3\xb3matas con pila deterministicos, a diferencia de lo que ocurr\xc3\xada con aquellos modelos, tiene una potencia descriptiva estrictamente menor. Para calificar a un aut\xc3\xb3mata con pila como deterministico deben darse dos circunstancias; en primer lugar, por supuesto, que en la definici\xc3\xb3n de cada componente de la funci\xc3\xb3n de transici\xc3\xb3n existan un \xc3\xbanico elemento lo que da la naturaleza determinista. Pero eso no es suficiente, pues adem\xc3\xa1s puede darse la circunstancia de que el aut\xc3\xb3mata est\xc3\xa9 en el estado  y en la pila aparezca el s\xc3\xadmbolo , entonces, si existe una definici\xc3\xb3n de transici\xc3\xb3n posible para alg\xc3\xban s\xc3\xadmbolo cualquiera  del alfabeto de entrada, pero, adem\xc3\xa1s existe otra alternativa para la palabra vac\xc3\xada , tambi\xc3\xa9n esto es una forma de no determinismo, pues podemos optar entre leer un s\xc3\xadmbolo o no hacerlo. Por eso, en aut\xc3\xb3mata deterministico no debe existir transici\xc3\xb3n posible con lectura de s\xc3\xadmbolo si puede hacerse sin ella, ni al contrario._NEWLINE_Para cada , se d\xc3\xa9 que:  , para cada\n_START_SECTION_\nAut\xc3\xb3mata con pila no determinista\n_START_PARAGRAPH_\nUn aut\xc3\xb3mata finito con pila no determinista (AFPN) consta de los mismos par\xc3\xa1metros de un AFPD._NEWLINE_P = (Q, \xce\xa3, \xd0\x93, \xce\x94, q0, T,Z):_NEWLINE_Donde la funci\xc3\xb3n de transici\xc3\xb3n \xce\x94 es de la forma:_NEWLINE_       \xce\x94: Q \xc3\x97 (\xce\xa3 U { \xce\xb5 }) \xc3\x97 \xd0\x93\xe2\x86\x92 Pf(Q \xc3\x97 \xd0\x93*)_NEWLINE_Donde Pf (Q\xc3\x97 \xd0\x93 *) es un conjunto de subconjuntos finitos de Q \xc3\x97 \xd0\x93*_NEWLINE_Para q \xd1\x94 Q, a \xd1\x94 \xce\xa3 U {\xce\xb5} y s \xd1\x94 \xd0\x93_NEWLINE_       \xce\x94 (q, a, s) = {(q1, \xce\xb31), (q2, \xce\xb3 2), . . . , (qn, \xce\xb3 n)}_NEWLINE_Donde \xce\xb3i \xd1\x94 \xd0\x93*'