Resumen
La teoría de autómatas es una materia básica en el área de la computación. Esta materia se ocupa del estudio de las máquinas de estados finitos que se utilizan como reconocedores de lenguajes. En cuanto a reconocedores, suponen la base para la construcción de compiladores y para el estudio de la computabilidad, esto es qué es capaz de computar una máquina actual y con qué complejidad. Por lo general, los textos que cubren esta materia, lo hacen desde un enfoque teórico proponiendo, para cada tema, una serie de ejercicios que debe resolver el lector. En esta materia es especialmente importante conocer la relación que existen entre las diferentes formas de representación de las diferentes máquinas teóricas existentes. El objetivo de este libro el de plantear ejercicios que recorran, para un mismo problema, todas las posibilidades de representación y sus equivalencias. No es objetivo de este libro presentar la base teórica que permita resolver estos ejercicios. Este libro sirve por tanto, de complemento para otros textos de contenido teórico. En cada capítulo se enunciarán los conocimientos teóricos necesarios para la resolución de los problemas planteados, así como las referencias que se pueden consultar para alcanzar dichos conocimientos. El libro se completa con ejercicios más cortos de carácter teórico/práctico que permite afianzar los conocimientos de esta materia. Como ayuda para la comprensión de los ejercicios expuestos en este texto se recomienda el uso de JFLAP, un programa gráfico implementando en Java que permite experimentar con lenguajes formales, gramáticas y autómatas (disponible en http://www.ia.uned.es/asignatura/aglf /)
