Qué añade la pila a un autómata finito
Un autómata finito solo recuerda una cosa: en qué estado está. Con k estados distingue como mucho k situaciones, y eso basta para muchísimas tareas —validar un formato, tokenizar código, buscar un patrón— pero no para nada que exija contar sin límite. Un autómata a pila (AFP, o PDA por pushdown automaton) le añade una memoria auxiliar con forma de pila: en cada transición mira el símbolo de entrada y el símbolo que hay en la cima, y decide a la vez a qué estado va y qué deja en la pila.
La pila es memoria ilimitada, pero de acceso restringido: solo se ve la cima. Esa restricción es la que separa a un autómata a pila de una máquina de Turing, que puede leer y escribir en cualquier punto de su cinta.
| Característica | Autómata finito (AF) | Autómata a pila (AFP) |
|---|
| Memoria | Solo el estado actual (finita) | El estado más una pila ilimitada |
| Qué mira para decidir | Estado y símbolo de entrada | Estado, símbolo de entrada y símbolo de la cima |
| Lenguajes que reconoce | Regulares (tipo 3) | Independientes del contexto (tipo 2) |
| Gramática equivalente | Regular / expresión regular | Gramática independiente del contexto (GIC) |
| ¿Reconoce aⁿbⁿ? | No (lema del bombeo) | Sí, con una A apilada por cada «a» |
| ¿Reconoce aⁿbⁿcⁿ? | No | Tampoco: una sola pila no lleva dos cuentas a la vez |
| ¿El no determinismo añade potencia? | No: todo AFND tiene un AFD equivalente | Sí: hay lenguajes que ningún AFP determinista reconoce |
| Uso típico en un compilador | Análisis léxico (tokens) | Análisis sintáctico (árbol de derivación) |
Por qué aⁿbⁿ no es regular — el lema del bombeo
El lema del bombeo dice que si un lenguaje es regular existe una longitud p tal que toda cadena del lenguaje de longitud al menos p puede partirse en tres trozos xyz, con y no vacía y xy de longitud como mucho p, de forma que xyⁱz sigue en el lenguaje para cualquier i ≥ 0.
Aplicado a aⁿbⁿ: toma la cadena aᵖbᵖ. Como xy mide como mucho p, el trozo y cae entero dentro del bloque de aes. Repetirlo dos veces produce más aes que bes, una cadena que ya no pertenece al lenguaje. La suposición era falsa: aⁿbⁿ no es regular. La intuición detrás del formalismo es simple — para comprobar que las cuentas cuadran hay que haberlas llevado, y un autómata finito no tiene dónde.
Con una pila el problema se desmonta en cinco transiciones: apila una A por cada «a», desapila una A por cada «b», y comprueba al final que solo queda el fondo. Es exactamente el primer ejemplo de esta página.
La jerarquía de Chomsky
| Tipo | Lenguajes | Máquina que los reconoce | Ejemplo |
|---|
| Tipo 3 | Regulares | Autómata finito | a*b* |
| Tipo 2 | Independientes del contexto | Autómata a pila | aⁿbⁿ, palíndromos, paréntesis equilibrados |
| Tipo 1 | Dependientes del contexto | Autómata linealmente acotado | aⁿbⁿcⁿ |
| Tipo 0 | Recursivamente enumerables | Máquina de Turing | El problema de la parada |
Cada nivel contiene estrictamente al anterior: todo lenguaje regular es independiente del contexto, pero no al revés. Los autómatas a pila ocupan el escalón intermedio, y de ahí que sean el paso natural después de los autómatas finitos en cualquier asignatura de teoría de la computación.
Los dos criterios de aceptación
Por estado final: se acepta si al terminar de leer la entrada el autómata está en un estado marcado como final, sin importar qué haya quedado en la pila. Por pila vacía: se acepta si al terminar de leer la entrada la pila ha quedado completamente vacía —fondo incluido—, y entonces los estados finales son irrelevantes; de hecho el autómata puede no tener ninguno.
Los dos criterios tienen la misma potencia, y se demuestra construyendo uno a partir del otro. Para pasar de pila vacía a estado final se añade un símbolo de fondo nuevo por debajo del original y un estado final al que se llega justo cuando ese símbolo nuevo aparece en la cima. Para el camino contrario se añade un estado que, desde cualquier estado final, vacía la pila con transiciones ε. El fondo nuevo hace falta para que el autómata no se quede sin pila a mitad de camino por accidente y acepte de más.
El segundo y el primer ejemplo de esta página son ese par: el mismo lenguaje aⁿbⁿ escrito de las dos maneras. Cárgalos y compara sus tablas — la única diferencia real está en la última transición.
Gramáticas independientes del contexto y compiladores
Un autómata a pila y una gramática independiente del contexto son dos formas de decir lo mismo: para toda GIC existe un AFP que reconoce su lenguaje, y viceversa. La gramática de aⁿbⁿ cabe en dos reglas: S → aSb | ab, y la de los palíndromos pares sobre {a,b} en tres: S → aSa | bSb | ε. La recursión de la gramática es lo que en el autómata hace la pila.
De ahí sale el reparto de tareas de un compilador. El análisis léxico —partir el texto en identificadores, números y operadores— se hace con autómatas finitos, porque un token no anida. El análisis sintáctico sí necesita anidamiento: paréntesis dentro de paréntesis, bloques dentro de funciones, expresiones dentro de expresiones. Los analizadores LL(1) y LR(1) que generan herramientas como Yacc, Bison o ANTLR son autómatas a pila deterministas, y su pila es literalmente la que en tiempo de ejecución acaba llamándose pila de llamadas.
Hay un límite que conviene tener presente: comprobar que una variable está declarada antes de usarse no es independiente del contexto. Por eso ningún compilador se queda en la gramática: después del árbol sintáctico viene el análisis semántico, con su tabla de símbolos.
Casos de uso reales
El ejercicio pide diseñar un AFP para un lenguaje y justificar por qué no es regular. Diseñar es fácil; comprobar que la tabla hace lo que crees, no tanto.
Escribe tu tabla, prueba tres cadenas del lenguaje y tres de fuera. Si acepta alguna que no debería, la traza te enseña por qué camino se coló.
Las preguntas clásicas son siempre las mismas: convertir entre los dos criterios de aceptación, o explicar por qué el no determinismo aquí sí añade potencia.
Carga los dos ejemplos de aⁿbⁿ y compáralos fila a fila: es la conversión entre criterios en su versión más pequeña posible.
Estás implementando un analizador de expresiones o un validador de estructuras anidadas y quieres entender qué modelo hay debajo de tu bucle con una pila.
Un validador de paréntesis equilibrados es un AFP de un solo estado: apila al abrir, desapila al cerrar, acepta con la pila vacía.
Explicar el no determinismo en la pizarra cuesta: hay que dibujar varias ramas a la vez y borrar las que mueren.
Con el ejemplo de palíndromos, prueba «abba» y luego «abab»: el primero acepta y el segundo agota todas las ramas. Ahí se ve que rechazar es más caro que aceptar.
Preguntas frecuentes
¿Por qué un AFP no determinista es más potente que uno determinista?
Porque hay lenguajes independientes del contexto que ningún AFP determinista reconoce, y el ejemplo canónico son los palíndromos pares ww^R: el autómata tiene que adivinar dónde acaba la primera mitad, y esa decisión no se puede tomar mirando solo el símbolo actual y la cima. Esto rompe la analogía con los autómatas finitos, donde AFD y AFND reconocen exactamente lo mismo.
Los lenguajes que sí reconoce un AFP determinista se llaman deterministas independientes del contexto, y son precisamente los que los generadores de parsers saben tratar.
¿Qué es exactamente el símbolo de fondo Z?
Es una marca que se coloca en la pila antes de empezar, y que en los libros suele llamarse Z₀. Sirve para dos cosas: saber que la pila está «vacía de contenido útil» sin quedarse de verdad sin nada que mirar, y tener una condición clara para la transición de cierre. Aquí la pila arranca siempre con Z.
En el ejemplo por pila vacía, la última transición desapila también el fondo: ahí es donde la pila queda literalmente en cero.
¿Qué significa que se apile «AZ» en una sola transición?
Que la cima se sustituye por esa cadena, con el primer carácter como nueva cima. Apilar AZ sobre una cima Z deja la pila con A arriba y Z debajo: es la forma habitual de decir «apila una A y conserva lo que había». Apilar solo Z deja la pila como estaba.
Escribir ε en ese campo (o dejarlo vacío) significa desapilar la cima sin poner nada en su lugar.
¿Por qué rechazar tarda más que aceptar?
Porque en un autómata no determinista aceptar solo exige encontrar un camino que funcione, y en cuanto aparece se puede parar. Rechazar exige demostrar que ningún camino funciona, o sea agotar el árbol entero de configuraciones. El contador de «configuraciones exploradas» del resultado enseña esa diferencia con números.
La exploración es en anchura, no en profundidad: con transiciones ε la profundidad se iría por una rama infinita, y además la anchura devuelve el camino aceptante más corto, que es el que interesa enseñar.
¿Qué quiere decir que la respuesta «no es concluyente»?
Que la exploración llegó al tope de configuraciones antes de agotar el árbol. Eso pasa cuando el autómata tiene un ciclo de transiciones ε que apila sin consumir entrada: la pila crece indefinidamente y siempre hay configuraciones nuevas. En ese caso el simulador se detiene y lo dice, en lugar de colgar el navegador o —peor— responder «rechazada» como si lo hubiera comprobado.
Si te sale ese aviso, busca transiciones con entrada ε que puedan repetirse sobre sí mismas y añade alguna condición sobre la cima que las corte.
Cómo diseñar un autómata a pila — paso a paso
1
Pregúntate qué hay que recordarSi basta con una propiedad acumulada de lo leído (paridad, último símbolo, si ya vi un patrón), no necesitas pila: es un lenguaje regular y un autómata finito basta. La pila solo hace falta cuando hay que recordar una cantidad o una secuencia sin límite.
2
Decide qué representa cada símbolo de la pilaEn aⁿbⁿ, cada A es «una b pendiente». En los paréntesis equilibrados, cada símbolo es un cierre pendiente. Si no sabes decir en una frase qué significa un símbolo de tu pila, el diseño todavía no está claro.
3
Separa las fases con transiciones εLa mayoría de estos autómatas tienen una fase de «llenado» y otra de «vaciado». El paso de una a otra suele ser una transición ε que no consume entrada, y es justo donde se concentra el no determinismo.
4
Elige el criterio de aceptación y sé coherenteSi aceptas por estado final, marca el estado final y no te preocupes por lo que quede en la pila. Si aceptas por pila vacía, asegúrate de desapilar también el fondo — es el fallo más común.
5
Prueba dentro y fuera del lenguajeTres cadenas que deben aceptarse (incluida la más corta) y tres que no: una demasiado larga por un lado, una con el orden cambiado y la cadena vacía. Un autómata que acepta de más falla en silencio, y solo se ve probando lo que no pertenece.
Consejos rápidos
🧱Conserva lo que habíaPara apilar sin destruir la cima, escribe en «apila» el símbolo nuevo seguido del que estaba: AZ, AA. Olvidar el segundo símbolo borra la pila poco a poco sin que se note.
🔍Cima ε no es lo mismo que cima ZCon cima ε la transición no mira la pila y tampoco la altera. Con cima Z exige que el fondo esté justo arriba, o sea que la pila esté vacía de contenido.
🪞La pila invierte por naturalezaLo último que entra es lo primero que sale, así que una pila compara una secuencia con su reflejo sin esfuerzo. Por eso los palíndromos son el ejemplo favorito de todos los libros.
🧭Empieza por un ejemplo que funcioneCarga aⁿbⁿ y cámbialo hasta tu lenguaje en vez de partir de una tabla en blanco. Ver qué rompe cada edición enseña más que acertar a la primera.
⏱️Cadenas cortas para trazarPara seguir la traza paso a paso, usa la cadena más corta del lenguaje. Con «ab» el camino aceptante son cinco configuraciones; con «aaaabbbb» son diecisiete y se pierde el hilo.
🚦Un solo estado inicialSi marcas varios, el simulador usa el primero y avisa. Es un despiste habitual al editar la lista de estados después de haber cargado un ejemplo.
- Aceptar por pila vacía y olvidar desapilar el símbolo de fondo: la cadena correcta se rechaza y la tabla parece bien escrita.
- Suponer que un AFP determinista basta. En autómatas finitos el no determinismo es una comodidad; aquí es potencia real, y los palíndromos lo demuestran.
- Creer que la pila permite contar dos cosas a la vez: aⁿbⁿcⁿ no es independiente del contexto, hace falta subir un escalón más en la jerarquía.
- Confundir «apila ε» con «cima ε». El primero desapila; el segundo ni mira ni toca la pila.
- Olvidar la cadena vacía. En el ejemplo de aⁿbⁿ de esta página no se acepta, porque para cambiar de fase hace falta una A en la cima; si quieres que pertenezca al lenguaje, hay que añadir una transición explícita.
- Dar por firme un «rechazada» que vino con el aviso de exploración truncada: ahí el simulador no ha terminado de mirar, y decirlo es parte de la respuesta.