Teoría de Lenguajes y Automatas

Propuestas de proyectos

• • Entorno simulado de un ecosistema. El objetivo es modelar distintos autómatas que modele el comportamiento de especies carnivoras, solitarias y en manada, especies herbivoras, etc., asi como condiciones cambiantes del medio. El sistema debe permitir variar la cantidad de individuos y especies del ecosistema y hacer estadisticas de natalidad, mortalidad, etc.

  • Detección de errores gramaticales o tipos de gramatica (en español o en ingles). Toda oración tiene una estructura gramatical compuesta segun su tipo, por ejemplo la mas simple como sujeto y predicado. De acuerdo a ciertas reglas se puede determinar si una oración esta correctamente escrita (Carlos esta corriendo) o no (Corre amarillo el carro). El sistema debe permitir identificar tipos de gramaticas de acuerdo a un conjunto fijo determinado, identificar las entidades en la oración y determinar segun su estructura que tipo de gramatica es si esta correctamente escrita o si esta mal formada.

  • Identificación de secuencias de ADN. En bioinformática es de vital interes identificar secuencias de cadenas de ADN una vez se ha realizado el secuenciamiento completo de una estructura biológica. Al finalizar el secuenciamiento se tienen una serie de letras (A-Adenina, C-Citosina, G-Guanina, T-Timina) que representan las bases que se concectan en la cadena de ADN. Un patron especifico de esta secuencia puede constituir un gen. Determinar el inicio y el fin de cada gen constituye una tarea dispendiosa que solo ha sido posible gracias a uso de los computadores en el area denominada como bioinformatica. El sistema debe perimitir encontrar una patron o un conjunto de patrones definidos para buscar en toda una secuencia de ADN de acuerdo a distintos grados de similitud (busqueda exacta, diferencia de una letra, dos, etc.), esto ultimo debido a que las mutaciones pueden ocurrir y alterar ligeramente el patrón normal de la secuencia lo cual es de utilidad para estudio de enfermedades con variabilidad genética.

  • El laberinto del Minotauro. Una de las aplicaciones de los autómatas finitos en el diseño de videojuegos, en este caso el juego recrea el mito griego de Teseo y el Minotauro, para ello el laberinto es un escenario desconocido inicialmente por el personaje Teseo pero bien conocido por el Minotauro. Cada uno de estos personajes debe ser modelado por un automata distinto. En este juego el objetivo es que Teseo busca y rescata a 7 griegos ofrecidos en sacrificio al minotauro que se encuentran en el laberinto antes que el Minotauro los encuentre y los mate, ademas Teseo debe luego buscar y matar al Minotauro para luego encontrar la salida. Teseo solo usa una antorcha que le permite ver a muy corta distancia lo que esta a su alrededor. El Minotauro tiene como unico objetivo matar bien sea un griego en sacrificio o al heroe Teseo para recuperar energia. El Minotauro no tiene antorcha pero para detectar la cercania de un humano solo puede sentir su rastro, para esto tanto los griegos como Teseo dejan "feromona" a su paso en cada casilla y con cada instante de tiempo esta se va evaporando poco a poco. De esta manera en caso de detectar feromona el Minotauro, este selecciona el camino donde es mas fuerte la marca, es decir mas reciente.

  • Juego de Estrategia tipo Era de los Imperios. Una de las aplicaciones de los autómatas finitos es en el modelado de personajes de videojuegos, asi como escenarios o dinamica del juego. En este caso el objetivo es modelar un prototipo de juego de estrategia donde puedan existir distintos tipos de guerreros de dos bandos con velocidad, fuerza y objetivos diferentes. Por ejemplo un tipo de guerrero es proteger a otro guerrero y otro tipo puede ser buscar un objeto. Para ello cada tipo de guerrero debe ser modelado por un automata y la dinamica del juego para determinar si termino o no tambien estara dada por un diagrama de estados. Este ultimo diagrama de estados puede ser no deterministico para incluir elementos que beneficie o no a alguno de los bandos como recuperar energia, aumento de guerreros o poderes para eliminar al azar enemigos.

  • Validación de un formulario Web. El objetivo es construir un formulario de captura que de acuerdo a una interfaz de administración sencilla e intuitiva perimita validar los campos de un formulario de datos a partir de expresiones regulares. Entre los campos los tipo fecha, hora, correo electrónico, direcciones web, cedula de ciudadania, nombres y apellidos, direcciones, codigos postales, numeros de telefono fijo y local, valor de sus ingresos anuales y/o mensuales, contraseña segura, numero de cuenta de ahorros, edad, fecha de nacimiento, etc. La interfaz administrativa debe ser similar a la interfaz de region y moneda de Windows permitiendo cambiar los parametros de fecha, moneda, etc. segun la región y formato seleccionado.

  • Extracción de información en la Web. El objetivo es desarrollar un programa que dada una o mas URLs sea capaz de detectar y guardar toda la información que pueda ser de interes como: enlaces web, enlaces de imagenes, fechas, horas, ciudades, paises, correos electrónicos, direcciones web, cedulas de ciudadania, direcciones, codigos postales, numeros de telefonos, datos tipo moneda, etc.

• Validador de codigo fuente. El objetivo es construir una aplicación capaz de determinar si un codigo fuente en un lenguaje de alto nivel especifico esta bien escrito o no. Debe tener el analisis lexico y semántico que valide por completo el código tanto en su sintaxis como en su estructura general.

Bibliografía

• • Hopcroft, John E. y Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación, CECSA, México, 1996.

  • J. G. Brookshear, Teoría de la Computación: Lenguajes Formales, Autómatas y Complejidad, Addison-Wesley Iberoamericana, 1993.

  • D. Kelley. Teoría de Autómatas y Lenguajes Formales. Prentice-Hall, 1995.

  • P. Isasi, P. Martínez y D. Borrajo. Lenguajes, Gramáticas y Autómatas. Un Enfoque Práctico. Addison-Wesley, Madrid, 1997.

  • M. Alfonseca, J. Sancho y M. Martínez. Teoría de Lenguajes, Gramáticas y Autómatas. Ediciones Universidad y Cultura, Madrid, 1990.

Recursos

• • Curso teoria de la computación. Rodrigo Di Castro. UNVirtual. http://www.virtual.unal.edu.co/cursos/ciencias/2001018/index.html [material]

  • [Murcia] TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES. Departamento de Ingeniería de la Información y las Comunicaciones. Universidad de Murcia. [pdf]

Software

• • Chalcharelo. http://www.ucse.edu.ar/fma/sepa/chalchalero.htm

  • Free-styler. Incluye plug-in de autómatas finitos. http://www.collide.info/index.php/FreeStyler

Lecturas

• • Penrose, Roger, La Nueva Mente del Emperador, Mondadori, 1991, ISBN 84-397-1786-5. [pdf] [amazon]