De los autómatas finitos a las expresiones regulares: un análisis áulico de identificación de expresiones equivalentes

Abstract

En el presente trabajo se propone una discusión acerca del análisis de expresiones regulares (ER), de estructuras sintácticas diferentes, que surgen a partir de la aplicación de una técnica de conversión de un autómata finito (AF) en dichas ER. Cada ER tiene una forma diferente, y por lo tanto parecen representar a lenguajes diferentes. La propuesta del trabajo es verificar esta diferencia, obteniendo como resultado que estas ER resultan ser equivalentes luego de implementar la minimización de los AF derivados a partir de cada una de ellas. Este análisis y validación surge desde la identificación en el trabajo áulico de la cátedra de Matemática Discreta con alumnos de las carreras de Licenciatura en Ciencias de la Computación y en Licenciatura de Sistemas de Información. Se realizó una experimentación utilizando el software de código abierto JFLAP, que permite sintetizar y relacionar los conceptos teóricos con la identificación práctica de la equivalencia entre las ER trabajadas. Además, se validó dicha equivalencia mediante la aplicación de propiedades algebraicas de las ER, permitiendo obtener el mismo resultado, de que las ER trabajadas son equivalentes a pesar de ser totalmente distintas.