Page 19 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 19
19
TEORÍA ALGEBRAICA DE LENGUAJES.
Cuando un autómata se usa para modelar la construcción de hardware (ej.: circuitos secuenciales)
o software (ej. analizadores léxicos) es muy importante examinar el problema de encontrar el
autómata mínimo equivalente a uno dado. Tanto Hoffman como Moore se ocuparon de este
problema y encontraron algoritmos prácticos para minimizar un autómata de estados finitos.
Para un autómata de n estados estos algoritmos requerían n2 pasos. Bastante más tarde, en 1971
Hopcroft encontró un método que lo hacía en o (n x log(n)) pasos. Existe un punto de vista
algebraico sobre la minimización y caracterización de autómatas finitos, debida a John Myhill y
Anil Nerode.
Kleene, en su intento de entender los trabajos de Mccullock y Pitts, abstrajo el concepto de
autómata finito a partir de las redes de neuronas y el concepto de expresión regular a partir del
cálculo lógico del modelo de Mccullock y Pitts. De la misma forma, Myhill a partir de los
conceptos de autómatas finitos de Kleene obtuvo el de diagrama de transición (deterministas) y a
los eventos los redujo a la unión de clases de equivalencia.
Siguiendo esta línea de trabajo, se ha elaborado en las últimas décadas una teoría abstracta de
autómatas con una fuerte base matemática que, según dijo Arbib en 1969, constituye “la
matemática pura de la informática”.
