Guía Docente 2020-21
LENGUAJES FORMALES

DATOS BÁSICOS DE LA GUÍA DOCENTE:

Materia: LENGUAJES FORMALES
Identificador: 30052
Titulación: GRADUADO EN INGENIERÍA INFORMÁTICA. PLAN 2008 (BOE 15/12/2008)
Módulo: TEORIA DE LA COMPUTACION
Tipo: OBLIGATORIA
Curso: 2 Periodo lectivo: Primer Cuatrimestre
Créditos: 3 Horas totales: 75
Actividades Presenciales: 33 Trabajo Autónomo: 42
Idioma Principal: Castellano Idioma Secundario: Inglés
Profesor: Correo electrónico:

PRESENTACIÓN:

Esta asignatura introduce modelos abstractos y matemáticos sobre los fundamentos de la computación. El estudio formal de la relación entre máquinas, lenguajes y gramáticas produce varios modelos de computación. Nos centraremos en tres clases de modelos: aquellos con una cantidad finita de memoria (autómatas finitos), modelos con memoria de tipo pila (autómatas de pila) y modelos no restringidos (máquinas de Turing).

COMPETENCIAS PROFESIONALES A DESARROLLAR EN LA MATERIA:

Competencias Generales de la titulación G05 Capacidad para adaptarse a diferentes entornos con una actitud positiva y optimista y orientar su conducta a la consecución de metas
G09 Capacidad para tomar decisiones de manera imparcial y desde un punto de vista racional
G15 Capacidad para estructurar la realidad relacionando objetos, situaciones y conceptos a través del razonamiento lógico matemático
Competencias Específicas de la titulación E02 Capacidad para aplicar los principios intrínsecos de la ingeniería basados en las matemáticas y en una combinación de disciplinas científicas
E03 Capacidad para reconocer los principios teóricos y aplicar satisfactoriamente los métodos prácticos apropiados para el análisis y la resolución de problemas de ingeniería
Resultados de Aprendizaje R01 Controlar los diferentes aspectos de la gramática formal
R02 Componer expresiones regulares y derivar los autómatas formales que las analicen
R03 Comprender las gramáticas libres de contexto
R04 Conocer las nociones básicas de teoría de la complejidad y las clases de problemas según su coste

REQUISITOS PREVIOS:

Sistemas Lógicos

PROGRAMACIÓN DE LA MATERIA:

Contenidos de la materia:

1 - Autómatas
    1.1 - Definición
    1.2 - AFD y AFN
    1.3 - Epsilon-transition
    1.4 - Equivalencia y simplificación
    1.5 - Conversión de AFN en AFD
2 - Expresiones Regulares y Lenguajes
    2.1 - Expresiones Regulares. Definición.
    2.2 - Autómatas y expresiones regulares
    2.3 - Propiedades de los lenguajes regulares
3 - Gramáticas
    3.1 - Definición
    3.2 - Ambigüedad y propiedades
    3.3 - Forma normal y de Chomsky
4 - Autómatas de pila y máquinas de Turing
    4.1 - Introducción
    4.2 - Autómatas de pila en lenguajes regulares
    4.3 - Introducción a máquinas de Turing

La planificación de la asignatura podrá verse modificada por motivos imprevistos (rendimiento del grupo, disponibilidad de recursos, modificaciones en el calendario académico, etc.) y por tanto no deberá considerarse como definitiva y cerrada.


METODOLOGÍAS Y ACTIVIDADES DE ENSEÑANZA Y APRENDIZAJE:

Metodologías de enseñanza-aprendizaje a desarrollar:

Volumen de trabajo del alumno:

Modalidad organizativa Métodos de enseñanza Horas estimadas
Actividades Presenciales
Clase magistral 14
Resolución de prácticas, problemas, ejercicios etc. 15
Actividades de evaluación 4
Trabajo Autónomo
Asistencia a tutorías 3
Estudio individual 18
Preparación de trabajos individuales 16
Lecturas obligatorias 5
Horas totales: 75

SISTEMA DE EVALUACIÓN:

Obtención de la nota final:

Pruebas escritas: 60 %
Trabajos individuales: 35 %
Participación: 5 %
TOTAL 100 %

*Las observaciones específicas sobre el sistema de evaluación serán comunicadas por escrito a los alumnos al inicio de la materia.

BIBLIOGRAFÍA Y DOCUMENTACIÓN:

Bibliografía básica:

KELLEY, D. (1995). Teoría de autómatas y lenguajes formales. Madrid: Prentice Hall, D.L. (ISBN 9780135187050)
MARTIN, J. (2004). Lenguajes Formales y Teoría de la Computación. México: McGraw-Hill. (ISBN 9789701045947)
ISASI, P., MARTÍNEZ, P., BORRAJO, D. (2001). Lenguajes, Gramáticas y Autómatas. Un enfoque práctico. Madrid: Addison-Wesley Iberoamericana, D. L. (ISBN 9788478290147) (con ejercicios resueltos)

Bibliografía recomendada:

HOPCROFT, J. E., MOTWANI, R., ULLMAN, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación, 2ª edición. Madrid: Pearson Educación. (ISBN 9788478290567)
ALFONSECA, M., SANCHO, J., MARTÍNEZ ORGA, M. (1997). Teoría de lenguajes, gramáticas y automátas. Madrid: Universidad y Cultura, D.L. (ISBN 8460560929)

Páginas web recomendadas:

JFLAP: graphical tools useful for basic concepts of Formal Languages and Automata Theory. http://www.jflap.org/


* Guía Docente sujeta a modificaciones