Guía Docente 2023-24 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:
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