Minimización de autómatas finitos

Abstract

El presente trabajo de investigacion tiene su base teórica dentro de la matemática discreta, la cual se desarrolló dentro del marco teórico, donde se presenta a un lenguaje como un conjunto de símbolos o cadenas definidas sobre un alfabeto y, un autómata finito determinista (AFD), es considerado como un modelo matemático de un determinado sistema, que trabaja con entradas y salidas. La importancia de este trabajo de investigacion, radica en el análisis y aplicación de una serie de herramientas matemáticas, que son la base teórica para la minimización de un determinado autómata finito. Este hecho se da de la siguiente manera: dado un autómata finito determinista, se define una relación de equivalencia sobre el conjunto de estados de dicho autómata finito determinista; los estados del nuevo autómata finito determinista que se construye, son las clases de equivalencia en que queda particionado el conjunto de estados. Luego, el nuevo autómata, es el autómata con el menor número de estados, que acepta el mismo lenguaje que el autómata finito determinista dado al inicio. Luego de los resultados obtenidos, se puede afirmar, que se determinaron las condiciones necesarias y suficientes para que un autómata finito pueda ser minimizado por medio de un algoritmo de minimización.