Download Programa de la asignatura - Universidad de La Serena

Teoria de Autómatas y Lenguajes Formales. (TALF-2008)
Prof. Dr. Eric Jeltsch F.
Programa de la asignatura TALF (270702, Plan nº 010)
TEL: 4-0-2
Prerrequisitos Informales:
Se espera que el alumno tenga sólida base en Programación Orientada a Objetos, así
como el manejo para abordar problemas de análisis y desarrollos matemáticos.
Prerrequisito Formal: 270603, Programación Avanzada.
Descripción de la Asignatura:
Es un curso del Ciclo Superior teórico- práctico, (7º Nivel) que entrega los fundamentos
teóricos de la programación, combinando la teoría con la práctica a través de numerosos
ejemplos. Se sigue la clasificación de Chomsky, se exponen las gramáticas regulares y los
autómatas finitos, las máquinas secuenciales, las gramáticas independientes del contexto
los autómatas a pila y las máquinas de Turing, junto con aplicaciones prácticas en
diversas disciplinas. Los tópicos seleccionados para las aplicaciones incluyen en general,
los sistemas inteligentes, modelamiento y reconocimiento de formas, el estudio y
construcción de compiladores, y en particular las gramáticas de grafos, gramáticas de
árboles, gramáticas de string y transductores. En los Laboratorios, se continua
aprendiendo y aplicando el lenguaje Java como herramienta y la Programación Orientada
a Objeto como metodología para implementar algoritmos o proyectos que se deriven de
los contenidos.
Objetivos:
Al término del curso el alumno podrá conocer, aplicar, diseñar e implementar conceptos
de los lenguajes formales para ponerlos en práctica y recrearlos en otras disciplinas,
usando el lenguaje de programación Java, así como el uso y evaluación de ciertas
herramientas y sistemas de software Open Source asociados a los contenidos con la
componente de visualización. En lo específico, el alumno deberá:
 Dominar las clases de lenguajes formales: ámbito, relaciones de contenidos y sus
respectivos dispositivos reconocedores / generadores (jerarquía de Chomsky).
 Manejar alguna herramienta o sistema de software asociado a los contenidos.
Metodología:
Para cumplir con los objetivos se utiliza una metodología de tipo Teórico - Práctico. Para
ello se realizan clases de teoría mediante la presentación de los contenidos, fundamentos
y algoritmos con ejemplos típicos de los temas. Para tal efecto, se mantiene un sitio Web
con material suplementario. Para la sección de Práctica se deja un material de apoyo. en
donde se basan las actividades a realizar durante los laboratorios. Las actividades se
realizan en forma semanal con una duración de 1 bloque (2 horas), por tal motivo, se
dejan actividades personales con una duración de 1 o 2 semanas, las que son evaluadas en
la hora de Laboratorio. Están programadas en total aprox. 14 sesiones de Laboratorios,
frente al PC, además de 7 evaluaciones.
Evaluaciones:
Teoría (3 Pruebas ) = 70%
Laboratorios (4 evaluaciones + Proyecto Final) = 30%.
NOTA: Como una forma de retroalimentación y marcar un estándar de las dificultades y
objetivos del curso es que se mantienen las Pautas de Corrección de pruebas anteriores,
_____________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
1
Teoria de Autómatas y Lenguajes Formales. (TALF-2008)
Prof. Dr. Eric Jeltsch F.
en la secretaría de la Escuela de Ingeniería en Computación en la carpeta del curso
TALF.
TEORIA - Contenidos
Cap. 0 Se entrega una introducción al curso y como el programa sustenta otras
asignaturas del plan de estudio de la carrera, así mismo se aborda el estado del arte de la
asignatura en un contexto global.
Cap. 1 Alfabeto, cadena de caracteres (string), Lenguajes, operaciones con Lenguajes,
Lenguajes Regulares. Expresiones aritméticas bien formadas como un ejemplo de
lenguaje formal.
Cap. 2 Máquinas abstractas, Máquinas de estado finito, Autómatas de estado finito
(AEF), Autómatas de estado finito determinista(AEFD) y no-determinista(AEFND),
Equivalencia entre AEFD y AEFND. Problema String Matching ( Rabin-Karp, con
autómatas, Knuth-Morris-Pratt, Boyer-Moore).
Cap. 3 Transductores. Autómatas Finitos con Salida. Máquina de Moore, Máquina de
Mealy, Equivalencia entre Moore y Mealy.
Cap. 4 Expresiones Regulares, Propiedades de los lenguajes regulares, Equivalencia
entre expresiones regulares y autómatas finitos.
Cap. 5 Gramáticas Formales, Jerarquerización de Chomsky, Gramáticas Regulares,
Características de los lenguajes aceptados por Autómatas de estado Finito ( unión,
concatenación, clausura de Kleene, complemento e intersección), Decidibilidad para los
Autómatas.
Cap. 7 Lenguajes no-regulares. Lema del Bombeo (Pumping Lema) para lenguajes
regulares, Homomorfismo entre lenguajes, Características de los lenguajes regulares
considerando homomorfismo. ( Prueba nº1, desde Cap. 0 - 7 ) (29 de Abril)
Cap. 8 Lenguajes de ContextoLibre(LCL), Gramáticas de Contexto Libre(GCL), Arboles
de derivación, Ambiguedad de gramáticas. Lema del Bombeo (Pumping Lema) para
LCL, Propiedades de los LCL.
Cap. 9 Propiedades de los LCL (unión, concatenación, clausura de Kleene,
complemento, homomorfismo). Representación de los Autómatas a Pilas.
Cap. 10 Formas Normales o estándares ( Chomsky, Greibach ), Relación entre AP y
AEF, Relación entre AP y GCL.
Cap. 11 Decidibilidad ( equivalencia, finitud, pertenencia) para los LCL, Algoritmo
Cocke-Younger-Kasami. ( Prueba nº2, desde Cap. 8 - 11 )(3 de Junio)
Cap. 12 Gramáticas de String y su interpretación en el “Problema de Reconocimiento de
Patrones en forma sintáctica”. Gramáticas de Árboles.
Cap. 13 Gramáticas de Lindenmayer y los sistemas DOL.
Cap. 14 Gramáticas y Autómatas Estocásticas y las Cadenas de Markov.
_____________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
2
Teoria de Autómatas y Lenguajes Formales. (TALF-2008)
Prof. Dr. Eric Jeltsch F.
Cap. 15 Gramáticas y Lenguajes de Grafos y sus Aplicaciones.
Cap.16 Máquinas de Turing, Tesis de Church. ( Prueba nº3, desde Cap. 12 – 16)(8 de
Julio)
Examen, corresponde a todos los contenidos, (fecha 14 de Julio).
Bibliografía: (1) texto guía, es decir 70% del curso está basado en él.
o
(1) Dean, Kelley, "Teoria de Autómatas y Lenguajes Formales", Prentice Hall, 1995.
o
C. Papadimitriou, H. Lewis, "Elements of the Theory of Computation", Prentice Hall,
1980.
o
Hopcroft, Ullman, "Introduction to Automata Theory, Languages and Computation",
Addison Wesley, 1981.
o
Cohen Daniel,"Introduction to Computer Theory", John Wiley & Sons, 1997.
o
M. Thomason, R. Gonzalez, "Syntactic Pattern Recognition: An Introduction",
Addison Wesley, 1978.
o
Cormen, Leiserson, Rivest, "Introduction to algorithms", McGraw-Hill, 1990.
o
Uwe, Schöning, "Theoretische Informatik kurz gefasst", BI, Wissenschaftsverlag,
1992.
o
Aho, Sethi, Ullman, "Compiladores", Addison Wesley, 1990.
o
G. Rozenberg, "Handbook of Graph Grammars and Computing by Graph
Transformation", World Scientific, 1997.
o
Przemyslaw Prusinkiewic, Aristid Lindenmayer “The Algorithmic Beauty of Plants “.
Springer-Verlag, 1990 (segunda edición 1996).
http://algorithmicbotany.org/papers/#abop(gratuita).
LABORATORIO - Contenidos
Se entrega una introducción de lo que se espera de los alumnos al término de la
asignatura con respecto a las habilidades que deberían desarrollar y la metodología a
seguir en el transcurso de los Laboratorios. Entre ellas está el de considerar las “buenas
prácticas en la ingeniería de software”, utilizando herramientas apropiadas de código
abierto, sobretodo aquellas que se relacionan con Análisis de requerimientos,
Especificación, Diseño y arquitectura, Programación, Prueba, Documentación,
Mantenimiento, entre otros.
Tema 1. Conocer, manejar y evaluar una herramienta de desarrollo, llamémoslo Entorno
de Desarrollo Integrado (IDE) que incluye un compilador y varias utilidades para la
depuración, en lenguaje Java. Prestar interés en la Ventana de Aplicación, Barra de
Menús, Barra de Herramientas, utilidades de depuración, acceso a otras ventanas de
aplicación, menú contextual y otros.
_____________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
3
Teoria de Autómatas y Lenguajes Formales. (TALF-2008)
Prof. Dr. Eric Jeltsch F.
Tema 2. Conocer diversas Application Program Interface, API de la distribución Java.
Tema 3. Conocer, manejar y evaluar herramienta de desarrollo orientadas al lenguaje
gráfico para visualizar, especificar, construir y documentar los distintos componentes de
un sistema de software, en donde UML proporciona un estándar.
Tema 4. Creación de un sistema de software que utilice los temas antes abordados. Los
sistemas podrán estar circunscritos en diversos temas, ya sea teóricos, o alguna otra
aplicación, como por ejemplo, Sistema de gestión, Sistema de Inventario, Sistema de
Decisión, Compiladores, Modelamiento de Sistemas, etc.
Tema 5. Conocer, manejar y evaluar una herramienta de desarrollo, llamémoslo Entorno
de Desarrollo Integrado (IDE) en el entorno de los contenidos teóricos. Para tal efecto se
dan, las siguientes direcciones.
1.
http://remus.rutgers.edu/~rhoads/links.html(Miscelaneo)
2.
http://www.informatik.uni-bremen.de/theorie/treebag/(TreeBag)
3.
http://www.uni-paderborn.de/fachbereich/AG/schaefer/ag_dt/PG/Fujaba/fujaba.html(Fujaba)
4.
http://mindstorms.lego.com (LEGOMind)
5.
http://www.informatik.uni-bremen.de/theorie/cs/ (CollageSystem)
6.
http://ist.unibw-muenchen.de/Tools/PROGRES/
7.
http://www.cpsc.ucalgary.ca/Redirect/bmv/lstudio(L-System)
8.
http://tfs.cs.tu-berlin.de/agg(AGG)
9.
http://www2.cs.fau.de/DiaGen/home.html(DiaGen)
10. http://www.cs.duke.edu/~rodger/tools/jflap/(JFLAP 4.0b10 Version
http://www.cs.duke.edu/%7Erodger/tools/jflap/)
11. http://www.cat.nyu.edu/~meyer/jasmin/(Java Assembler Interface)
12. http://www.cs.princeton.edu/~appel/modern/java/JLex/
13. http://www.cs.princeton.edu/~appel/modern/java/CUP/
14. http://www.gentleware.com/products/index.php3(Herramienta-UML)
15. http://www.magicdraw.com/(Herramienta-UML)
16. http://www.togethersoft.com/(Herramienta-UML)
17. http://cui.unige.ch/eao/www/Visual/Visual.Programming.biblio.html (The Virtual Library Page on
Visual Languages: )
18. http://www.cs.orst.edu/~burnett/vpl.html(The Virtual Library Page on Visual Languages: )
19. http://www.cs.rpi.edu/~buschc/(Graphviz - open source graph drawing software)
20. Turing machine simulator (links proporcionado por Eric Thomas):
_____________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
4
Teoria de Autómatas y Lenguajes Formales. (TALF-2008)
Prof. Dr. Eric Jeltsch F.
Código de Honor: Todo trabajo, ya sea exposición, informe o alguna otra actividad
evaluativa, el alumno deberá incluir y respetar lo siguiente:
a) agradecer y mencionar la (o las) fuente(s) de información de la (o las)
persona(s) que le colaboraron en su presentación, tanto en su contenido como en
la presentación.
b) mencionar la (o las) fuente(s) de información del (o los) enlace(s) de Internet
que le sirvieron de inspiración en su presentación. Entendiendo que lo logrado
es una "adaptación" de lo mencionado en la página Web y no una copia o
traducción de lo allí mencionado.
c) basado en lo anterior, cualquier otra forma de presentar un trabajo, y
habiéndose constatado el no cumplimiento de los preceptos antes descritos. El (o
los) alumno(s) recibirán la nota mínima, es decir 1.0.
_____________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
5