Guía Docente 2019-20
LENGUAJES FORMALES

BASIC DETAILS:

Subject: LENGUAJES FORMALES
Id.: 30529
Programme: GRADUADO EN INGENIERÍA INFORMÁTICA (SEMIPRESENCIAL). 2008 (BOE 15/12/2008)
Module: TEORÍA DE LA COMPUTACIÓN
Subject type: OBLIGATORIA
Year: 2 Teaching period: Primer Cuatrimestre
Credits: 3 Total hours: 75
Classroom activities: 9 Individual study: 66
Main teaching language: Castellano Secondary teaching language: Inglés
Lecturer: Email:

PRESENTATION:

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 tipo pila (autómatas de pila) y modelos no restringidos (máquinas de Turing).

PROFESSIONAL COMPETENCES ACQUIRED IN THE SUBJECT:

General programme competences G05 Capacity to adapt to different environments while being positive and optimistic, orienting your behaviour towards the achievement of goals.
G09 Capacity to make decisions impartially and rationally.
G15 Capacity to structure reality by means of linking objects, situations and concepts through logical mathematical reasoning.
Specific programme competences E02 Capacity to apply the intrinsic engineering principles based on mathematics and a combination of scientific disciplines.
E03 Capacity to recognise the technical principles and apply the appropriate practical methods satisfactorily to analyse and solve engineering problems.
Learning outcomes R01 Master the different aspects of formal grammar.
R02 Write regular expressions and derive the formal automatons which analyse them.
R03 Understand the context-free grammars.
R04 Know the basic notions about complexity theory and the kinds of problems depending on their cost.

PRE-REQUISITES:

Ninguno

SUBJECT PROGRAMME:

Observations:


La programación de la materia sigue el guión de la colección de apuntes desarrollada por el Profesor Los Santos, que se publica en la PDU.

Subject contents:

1 - Autómatas
    1.1 - Definición
    1.2 - DFA y NFA
    1.3 - e-transition
    1.4 - Equivalencia y simplificación
    1.4 - Equivalencia y simplificación
    1.5 - Paso de NFA a DFA
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 de libre contexto
    3.1 - Definición
    3.2 - Ambigüedad y propiedades
    3.3 - Lema del bombeo
    3.4 - Forma normal y Chomsy
4 - Autómatas de pilas y máquinas Turing
    4.1 - Introducción
    4.2 - Autómatas de pila en lenguajes regulares
    4.3 - Introducción a máquinas de Turing

Subject planning could be modified due unforeseen circumstances (group performance, availability of resources, changes to academic calendar etc.) and should not, therefore, be considered to be definitive.


TEACHING AND LEARNING METHODOLOGIES AND ACTIVITIES:

Teaching and learning methodologies and activities applied:

Explicación teórica. El profesor expondrá apoyado en recursos TIC (tablet, proyector, Internet) y la pizarra la parte teórica de la asignatura. Las sesiones teóricas serán acompañadas por ejercicios para aplicar los conocimientos teóricos. Se valorará la participación,debate, preguntas e inquietudes mostradas por los alumnos relacionadas con la asignatura.
 
Resolución de ejercicios. Aprendizaje basado en resolución de ejercicios y problemas Los contenidos teóricos se apoyan en la resolución de problemas que serán propuestos por el profesor y resueltos por los alumnos. Algunos de estos problemas serán solucionados por los alumnos como parte de su trabajo autónomo.
 
Sesiones de tutoría. Los estudiantes podrán preguntar al profesor aquellas dudas que no han podido ser resueltas durante las clases o que hayan surgido en su tiempo dedicado al trabajo autónomo.También habrá disponible un foro en la PDU (Plataforma Docente universitaria) que podrá ser utilizado para plantear dudas sobre la asignatura, lo cual será evaluado positivamente como parte de la participación del alumno.
 

Student work load:

Teaching mode Teaching methods Estimated hours
Classroom activities
Master classes 3,5
Practical work, exercises, problem-solving etc. 5,5
Individual study
Tutorials 5
Individual study 27
Individual coursework preparation 25
Research work 1
Other individual study activities 5
Exam 3
Total hours: 75

ASSESSMENT SCHEME:

Calculation of final mark:

Written tests: 30 %
Individual coursework: 30 %
Group coursework: 5 %
Final exam: 35 %
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.

BIBLIOGRAPHY AND DOCUMENTATION:

Basic bibliography:

John Martín. Lenguajes Formales y Teoría de la Computación, McGraw-Hill ManuelD. Kelly Teoría de autómatas y lenguajes formales, Prentice-Hall, 1995.
P. Isasi, P. Martínez, D. Borrajo Lenguajes, gramáticas y autómatas. Un enfoquepráctico, Addison-Wesley, 1997.

Recommended bibliography:

J.E. Hopcroft, R. Motwani, J.D. Ullman Introducción a la Teoría de Autómatas,Lenguajes y Computación, 2a edición, Addison-Wesley Iberoamericana, 2002.

Recommended websites:


* Guía Docente sujeta a modificaciones