José Luis Cruz Suárez
Andrea Sánchez Castrillón
1. Introducción
Los autómatas son dispositivos abstractos que pueden tomar una entrada y cambiar de
estado en respuesta a esa entrada. Un autómata de pila es una extensión de un autómata
finito con la adición de una pila, que proporciona memoria adicional. En este informe se
aborda la implementación de un autómata de pila con la finalidad de reconocer el lenguaje
L = {a^n b c^n d, n >= 0} y su visualización conforme a su funcionamiento a través de una
animación gráfica tal como fue propuesto.
2. Teoría
Autómata de Pila: Un autómata de pila es una máquina de estado finito que puede hacer
uso de una pila para almacenar información adicional. Consiste en un conjunto finito de
estados, un alfabeto de entrada, un alfabeto de pila y una función de transición.
Lenguaje L = {a^n b c^n d, n >= 0}: Este lenguaje consiste en cadenas de la forma "a^n b
c^n d", donde la cantidad de 'a' es igual a la cantidad de 'c' y no hay restricción en la
cantidad de 'b' o 'd'.
3. Objetivo
El objetivo de este proyecto es implementar un autómata de pila que reconozca el
lenguaje L = {a^n b c^n d, n >= 0} y visualizar su funcionamiento mediante una animación
gráfica que muestre los estados del autómata y el contenido de la pila en cada paso.
4. Desarrollo
Implementación del Autómata de Pila: Se ha desarrollado una implementación del
autómata de pila en Python utilizando una clase AutomataPila. Esta clase incluye métodos
para realizar transiciones entre estados y procesar cadenas de entrada.
Visualización Gráfica: Se ha utilizado la biblioteca matplotlib para generar una animación
gráfica que muestra los estados del autómata y el contenido de la pila en cada paso del
procesamiento de la cadena de entrada.
5. Conclusiones
Se ha logrado implementar un autómata de pila para reconocer el lenguaje L = {a^n b c^n
d, n >= 0}.
La visualización gráfica proporciona una forma intuitiva de comprender el funcionamiento
del autómata y cómo cambia el contenido de la pila en cada paso.
Este proyecto demuestra la utilidad de los autómatas de pila en la resolución de
problemas de reconocimiento de lenguajes formales y la importancia de la visualización
gráfica para comprender el comportamiento de los autómatas en tiempo real.
1. El funcionamiento de este autómata en función de su grafica sigue los siguientes
pasos:
Inicialización: El autómata comienza en el estado inicial q0 con una pila vacía.
2. Procesamiento de la Cadena: A medida que se procesa la cadena de entrada, el
autómata realiza transiciones entre estados según las reglas definidas en la
función de transición.
3. Actualización de la Pila: Durante cada transición, el autómata puede realizar
operaciones de apilado (apilar) o desapilado (desapilar) en la pila, dependiendo
de las reglas de transición y el símbolo de entrada actual.
4. Finalización: Una vez que se ha procesado toda la cadena de entrada, el
autómata alcanza un estado final. Si la pila está vacía en este punto y el estado
actual es un estado final (en este caso, q2), la cadena se acepta; de lo contrario, la
cadena se rechaza.