Requisitos Previos

Es muy recomendable que el alumno haya adquirido las competencias correspondientes a las materias de los semestres anteriores.

En particular, el alumno debe haber superado un porcentaje significativo de las materias/asignaturas de los módulos de formación básico y común. En todo caso, el alumno debería tener cierta madurez matemática, del nivel de asignaturas como Álgebra y Matemática Discreta. Igualmente debería dominar el lenguaje de programación C y ser capaz de implementar código que simule modelos de pequeña complejidad. Los conocimientos necesarios son los adquiridos en las asignaturas con contenidos de programación del primer curso del grado.

Recomendaciones

Se recomienda al alumno el estudio y el trabajo continuado, así como la implementación práctica sobre un ordenador de los algoritmos y programas que se enseñan en esta asignatura.

Documento	Primer Apellido	Segundo Apellido	Nombre	Categoria	Coordinador
70864384G	DORRONSORO	DIAZ	BERNABE	CATEDRÁTICO/A DE UNIVERSIDAD

Id. Compentencia	Orden	ID	Resultado formación y aprendizaje	Competencia
33146	2	CB2	Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio	COMPETENCIA GENERAL
33149	2	CB5	Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía	COMPETENCIA GENERAL
29067	3	CO02	Capacidad para conocer los fundamentos teóricos de los lenguajes de programación y las técnicas de procesamiento léxico, sintáctico y semántico asociadas, y saber aplicarlas para la creación, diseño y procesamiento de lenguajes	COMPETENCIA ESPECÍFICA
29072	2	CG09	Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.	COMPETENCIA GENERAL
33150	4	CT1	Trabajo en equipo: capacidad de asumir las labores asignadas dentro de un equipo, así como de integrarse en él y trabajar de forma eficiente con el resto de sus integrantes	COMPETENCIA TRANSVERSAL

ID/ Orden	Resultado
1	Modelar procesadores de lenguajes utilizando la teoría de autómatas finitos (en sus versiones determinista y no determinista) que reconozcan a lenguajes regulares dados. Aplicar los métodos de transformación entre las diferentes clases de autómatas finitos. Minimizar autómatas finitos.
2	Saber diseñar e implementar un lenguaje de programación a nivel léxico.
3	Desarrollar tabularmente la Jerarquía de Chomsky y ser capaz de listar sus implicaciones teóricas. Saber diseñar lenguajes libres de contexto mediante gramáticas y autómatas de pila, y conocer los algoritmos de transformación entre ambos.
4	Saber diseñar un lenguaje de programación a nivel sintáctico así como implementar un analizador sintáctico: tanto ascendente como descendente; conociendo sus fundamentos teóricos y sus limitaciones.
6	Saber utilizar herramientas de ayuda a nivel léxico y sintáctico.
7	Saber demostrar si un lenguaje es regular o no. Describir un lenguaje regular mediante expresiones regulares y autómatas finitos, y aplicar los algoritmos para ttransformar de expresión regular a un autómata finito y viceversa.

Total de actividades de docencia presencial:

Total de otras actividades:

Total de la asignatura:

Tipo actividad formativa	Código	Descripción	Horas	Detalle
1	01	Teoría	20
2	02	Prácticas, seminarios y problemas	10	Resolución de problemas en clase.
3	03	Prácticas de informática	30	Prácticas de laboratorio con el ordenador. Podrán ser individuales o en pequeños grupos
10	10	Actividades formativas no presenciales	86,00	a) Estudio continuado de la asignatura. b) Realización de prácticas individuales con el ordenador. c) Realización de proyectos individuales o en pequeños grupos. d) Resolución de los ejercicios propuestos por el profesor.
12	12	Actividades de evaluación	4,00	Pruebas teóricas y prácticas finales

Procedimientos de Evaluación

ID/ Orden	Tarea / Actividad	Medios, Técnicas e Instrumentos	Ponderación
1	Prácticas sobre ordenador	Entrega de los programas y documentación requerida a través del campus virtual	20 %
2	Examen final con cuestiones sobre los contenidos teóricos y prácticos.	Examen final escrito	60 %
3	Desarrollo de un proyecto en grupo	Memoria y documentación del proyecto (en grupos pequeños).	20 %

Criterios de Evaluación

Los alumnos deben entregar las prácticas y ejercicios pedidos en el tiempo especificado (trabajo individual). De entre todos los trabajos y prácticas entregadas dos serán evaluadas y supondrán un 20% de la calificación final.

También se realizará un proyecto (trabajo en pareja). La calificación será el 20% de la nota final.

Además, se realizará un examen final teórico, que consistirá de preguntas y ejercicios escritos, cubriendo la mayoría de los contenidos de la asignatura. El alumno debe contestar a todas las preguntas demostrando dominar, suficientemente, todos los objetivos básicos de la asignatura. El examen supondrá un 60% de la nota final.

Será necesario obtener al menos un 5 sobre 10 en cada una de las tres partes evaluables de la asignatura (prácticas, proyecto y examen), de forma independiente, para superar la asignatura. En caso de no obtener un 5 sobre 10 en todas las partes, el alumno suspenderá la asignatura. La calificación final de la asignatura será calculada según lo dispuesto en el art 15.3 del Reglamento de Evaluación de la UCA.

El alumno tendrá derecho a una prueba de evaluación global, según normativa. Esta prueba deberá ser solicitada al profesor a través del campus virtual en los plazos que el Centro determine, y constará de un examen, cuyo valor será el 60% de la calificación final, y las prácticas y el proyecto evaluados, que son el 20% y el 20% de la calificación, respectivamente. La calificación en el examen debe ser mayor que 5 (sobre 10) para superar la asignatura. En caso de no superar la asignatura, la calificación final será calculada según lo dispuesto en el art. 15.3 del Reglamento de Evaluación. Se guardará durante el curso la calificación obtenida para las prácticas y/o el proyecto si es mayor que 5, y el alumno siempre podrá hacerlas de nuevo si quiere ser reevaluado. En las convocatorias distintas de la natural, las prácticas y el proyecto deberán ser entregadas al profesor a través del campus virtual, con fecha límite el día del examen.

Los criterios de evaluación considerados se resumen a continuación:
- Conocimiento sobre la teoría de autómatas y lenguajes formales
- Organización, claridad, elegancia y corrección de los algoritmos e implementaciones presentadas
- Participación e implicación en el trabajo en equipo
- Corrección ortográfica y gramatical escrita y oral

En el examen, el alumno debe describir correctamente, detalladamente, y justificadamente los desarrollos que llevan a la solución de los problemas propuestos. El alumno debe resaltar claramente el resultado a los problemas/preguntas propuestos. La solución al problema sin el desarrollo que ha llevado a dicha solución no se tomará como válida.

En cuanto a los algoritmos y programas desarrollados, deben realizar su función (compilarse en un ordenador, ejecutarse etc.). Además se valorará su eficiencia, coherencia interna, correcta estructuración de los mismos, limpieza de código y estilo de los comentarios.

En cuanto a presentación y expresión, se valorarán la claridad y la precisión, así como la adecuada organización de los contenidos expuestos.

El inglés se utilizará como lengua vehicular en los trabajos presentados durante la evaluación continua. La mayoría del material ofrecido al alumno estará en inglés.

La copia total o parcial de exámenes o prácticas, así como cualquier otro tipo de fraude detectado por los profesores, podrá ser motivo de SUSPENSO INMEDIATO EN TODAS LAS CONVOCATORIAS del curso académico para todos los implicados, sea cual fuere su papel. En particular, se informa de que las entregas electrónicas podrán almacenarse durante un plazo de 5 años para ulteriores comprobaciones.

ID/ Orden	Temario	Descripción
1	TEMA 1: Introducción. - Introducción a la teoría de autómatas y lenguajes formales - Motivación - Ejemplos y ejercicios
2	TEMA 2: Autómatas finitos deterministas. - Alfabetos, cadenas y lenguajes - Tablas de transición - Lenguajes regulares - Minimización de autómatas finitos deterministas - Equivalencia de autómatas finitos deterministas
3	TEMA 3: Autómatas finitos no deterministas. - No-determinismo - Equivalencia entre autómatas finitos deterministas y autómatas finitos no deterministas - Transiciones épsilon
4	TEMA 4: Expresiones regulares y sus propiedades. - Definición - Equivalencia entre autómatas finitos deterministas y expresiones regulares - Pasar de autómata finito determinista a expresión regular - Pasar de expresión regular a autómata finito determinista
5	TEMA 5: Lenguajes regulares - Introducción - Propiedades de decisión - Propiedades de cierre
6	TEMA 6: Gramáticas - Introducción - Jerarquía de Chomsky - Gramáticas regulares - Gramáticas libres del contexto - Árboles de análisis - El arte de diseñar gramáticas
7	TEMA 7: Análisis descendente y ascendente - Análisis descendente - Análisis ascendente
8	TEMA 8: Autómatas a pila - Definición - Movimientos en un autómata a pila - El lenguaje de un autómata a pila - Autómata a pila determinista

Bibliografía

Bibliografía Básica

* John E. Hopcroft & R. Motwani & Jeffrey D. Ullman. “Teoría de autómatas, lenguajes y computación. 3ª ed.” Pearson Educación 2008.
* José Antonio Jiménez Millán. "Compiladores y Procesadores de Lenguajes. 2ª ed.". Edita: Servicio de Publicaciones de la Universidad de Cádiz, 2010.
* Alfred V. Aho, Monica Lam, Ravi Sethi, Jeffrey D. Ullman. "Compiladores: Principios, Técnicas y Herramientas 2ª edición". Edita: Addison-Wesley, 2008.
* Pedro Isasi Viñuela, Paloma Martínez Fernández, Daniel Borrajo Millán. "Lenguajes, gramáticas y autómatas : un enfoque práctico", Addison Wesley, 1997
* Elena Gaudioso Vázquez, Tomás García Saiz. "Introducción a la teoría de autómatas, gramáticas y lenguajes", Centro de Estudios Ramón Areces, 2017.
* Dick Grune, Ceriel J.H. Jacobs, Parsing Techniques – A Practical Guide, Springer, 2008

Bibliografía Específica

Manuales de SLY:
• https://sly.readthedocs.io/en/latest/sly.html
• https://docs.python.org/3/howto/regex.html

Bibliografía Ampliación
* Andrew W. Appel and Maia Ginsburg, Modern Compiler Implementation in C (Tiger Book), Cambridge University Press, 2002
* Dean Kelley, Teoría de Autómatas y Lenguajes Formales, Prentice-Hall, 1995
* Dexter C. Kozen, Automata and Computability, Springer, 1997
* Harry Lewis, Christos Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1998.
* Michael Sipser, Introduction to the Theory of Computation, third edition, Thomson Course Technology, 2012

UniversidaddeCádiz

Programa Docente de 21714027 - TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES