Última actualización: 27/07/2021


Curso Académico: 2021/2022

Teoría de autómatas y lenguajes formales
(13877)
Titulación: Grado en Ingeniería Informática (218)


Coordinador/a: SANCHIS DE MIGUEL, MARIA ARACELI

Departamento asignado a la asignatura: Departamento de Informática

Tipo: Obligatoria
Créditos: 6.0 ECTS

Curso:
Cuatrimestre:




Requisitos (Asignaturas o materias cuyo conocimiento se presupone)
Programación Estructuras de Datos y Algoritmos
Competencias y resultados del aprendizaje
Descripción de contenidos: Programa
1.Introducción a la teoría de Autómatas y Lenguajes Formales. 1.1. Por qué de la Teoría de Autómatas. Historia y Origen 1.2. Relación con otras Áreas de Conocimiento. 1.2. Máquinas, Lenguajes y Algoritmos. 2.- Teoría de Autómatas 2.1.Introducción y Definiciones. 2.2 Modelo Matemático de un Autómata 2.3 Autómatas y Algoritmos 2.4 Autómatas discretos, continuos e hibridos. 2.5 Clases de Autómatas 3.Autómatas Finitos 3.1. Definición y representación de Autómatas Finitos Deterministas (AFD) 3.2. AFD como reconocedores de lenguajes 3.3. Equivalencia y minimización de AFD 3.4. Teoremas sobre AFD 3.5. Definición y representación de Autómatas Finitos No Deterministas (AFND) 3.6. Lenguaje aceptado por un AFND 3.7. Equivalencia entre AFD y AFND 4.Lenguajes y Gramáticas formales. 4.1. Operaciones con Palabras. Operaciones con Lenguajes. Reglas de Derivación 4.2. Concepto de Gramática. Definición de Gramática Formal 4.3. Jerarquía de Chomsky y Gramáticas Equivalentes 4.4. Gramáticas Independientes del Contexto (Tipo 2) 4.5. Lenguaje Generado por una Gramática Tipo 2. Arboles de Derivación 4.6. Gramáticas Bien Formadas 4.7. Forma Normal de Chomsky. Forma Normal de Greibach 5.Lenguajes regulares. 5.1. Definición de Lenguajes regular 5.2. AFD asociado a una Gramática de Tipo 3 5.3. Expresiones Regulares. Equivalencias 5.4. Teoremas de Kleene 5.5. Ecuaciones características 5.6. Algoritmo recursivo de síntesis 5.7. Derivada de una expresión regular 6.Autómatas a pila. 6.1.Definición de Autómata a Pila (AP) 6.2.Movimientos y Descripciones Instantáneas en AP 6.3.AP por vaciado (APV) y AP por estados finales (APF) 6.4.Lenguaje aceptado por un AP: equivalencia APV y APF 6.5.Construcción de APV a partir de una Gramática Tipo 2 6.6.Construcción de una Gramática Tipo 2 a partir de AP 7.Máquina de Turing 7.1.Definición de la Máquina de Turing 7.2.Variaciones de la Máquina de Turing 7.3.Máquina de Turing Universal 8. Complejidad Computacional 8.1 Teoría de la Complejidad 8.2.Complejidad de Algoritmos 8.3.Problemas P versus NP 8.4 Clases de Complejidad 8.5 Complejidad temporal 8.6 Teoremas de jerarquía 8.7 Problemas no computacionales 8.8 Límites de la Computación
Actividades formativas, metodología a utilizar y régimen de tutorías
CLASES TEÓRICO-PRÁCTICAS (contenido teórico): 3.5 ECTS. En ellas se presentarán los conocimientos que deben adquirir los estudiantes. Éstos recibirán las notas de clase y tendrán textos básicos de referencia para facilitar el seguimiento de las clases y el desarrollo del trabajo posterior. Se resolverán ejercicios por parte del estudiante que le servirá de autoevaluación y para adquirir las capacidades necesarias. Clases de problemas, en las que se desarrollen y discutan los problemas que se proponen a los estudiantes. TALLERES Y/O PRÁCTICAS DE LABORATORIO. 1,5 ECTS Desarrollados con o sin presencia del profesor, tienen por objetivo completar e integrar el desarrollo de todas las competencias específicas y transversales, en la resolución de dos casos prácticos donde queden bien documentados el planteamiento del problema, la elección del método de resolución, los resultados obtenidos y la interpretación de los mismos. EXAMEN FINAL. 0,5 ECTS Se valorarán de forma global los conocimientos, destrezas y capacidades adquiridas a lo largo del curso. TUTORÍAS. 0,5 ECTS Asistencia individualizada (tutorías individuales) o en grupo (tutorías colectivas) a los estudiantes por parte del profesor
Sistema de evaluación
  • Peso porcentual del Examen Final 50
  • Peso porcentual del resto de la evaluación 50
Calendario de Evaluación Continua
Bibliografía básica
  • Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón.. Teoría de autómatas y lenguajes formales.. McGraw-Hill (2007)..
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman.. Introduction to Automata Theory, Languages, and Computation (Third Edition). Pearson Education, Pearson Addison Wesley.
  • Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga.. Teoría de lenguajes, gramáticas y autómatas.. Publicaciones R.A.E.C. ISBN: 8460560929. 1997..
  • Pedro Isasi, Paloma Martínez y Daniel Borrajo.. Lenguajes, Gramáticas y Autómatas. Un enfoque práctico.. Addison-Wesley, (1997).
  • Susan H. Rodger and Thomas W. Finley.. JFLAP: An Interactive Formal Languages and Automata Package. 2006. Jones & Bartlett Publishers, Sudbury, MA. ISBN 0763738344.
Bibliografía complementaria
  • Brookshear, J. Glenn.. Teoría de la computación : lenguajes formales, autómatas y complejidad.. Addison Wesley Iberoamericana. 1993. ISBN: 9684443846.
  • Jeffrey Shallit.. A Second Course in Formal Languages and Automata Theory.. Cambridge University Press, September 30 2008..
  • Michael Sipser.. Introduction to the Theory of Computation (2nd Edition) 2006. Thomson Course Technology..
  • Peter Linz. An Introduction to Formal Languages and Automata. Third Edition. Jones and Bartlett Publishers. ISBN: 0763714224..
  • R. Penrose. La Nueva Mente del Emperador. Mondadori, 1991..

El programa de la asignatura podría sufrir alguna variación por causa de fuerza mayor debidamente justificada o por eventos académicos comunicados con antelación.