Programa docente base
Teoría de Autómatas y Lenguajes Formales

20 de febrero de 2005

Datos administrativos de la Universidad

Asignatura

Código de la materia	106122240
Nombre de la materia	Teoría de Autómatas y de Lenguajes Formales
Centro/Titulación	Escuela Superior de Ingeniería Informática/Ingeniería Informática
Curso	segundo
Cuatrimestre	segundo
Tipo	obligatoria
Créditos aula/grupo	4.5
Créditos laboratorio/grupo	1.5
Créditos prácticas/grupo	0
Número grupos aula	2
Número grupos laboratorio	7
Número grupos prácticas	0
Anual/Cuatrimestral	Cuatrimestral
Departamento	Informática
Área de conocimiento	Área de Lenguajes y Sistemas Informáticos
Horario:	mira abajo
Área:	Lenguajes y Sistemas Informáticos

Profesorado de la materia

Profesor	Desp.	Crd.	Tutorías
Arno Formella	309	7.5	mira Web de Profesores
Pilar Carrión Pardo	409	7.5	mira Web de Profesores
Lourdes Borrajo Diz	307	3	mira Web de Profesores
José Manuel Rdgz Rdgz

Horarios

	Lunes	Martes	Miércoles
9-10		TALF(A) 22
10-11	TALF(A1) 10
11-12	TALF(A2) 10	TALF(B7) 10	Tutorías (Teoría)
12-13	TALF(A) 22		Tutorías (Teoría)
13-14	TALF(A) 22		Tutorías (Teoría)
14-15
15-16
16-17	TALF(B)/TALF(A3) 22/10	TALF(B) 22	Tutorías (Teoría)
17-18	TALF(B)		Tutorías (Teoría)
18-19	TALF(AB4) 40		Tutorías (Teoría)
19-20	TALF(B5) 40
20-21	TALF(B6) 40

Temario de la materia

Previo

No se asume ningún conocimiento previo especial a parte de conocimientos básicos tanto en matemáticas como en la programación.

Objetivos de la materia

Los principales objetivos de la asignatura son:

• comprender los fundamentos básicos de los lenguajes formales, sus propiedades y mecanismos de representación
• entender el funcionamiento de las gramáticas como generadores de lenguajes y diferenciar sus tipos
• destacar el papel de los autómatas en el reconocimiento de lenguajes y distinguir entre los diferentes tipos de autómatas
• relacionar tipos de lenguajes con autómatas y gramáticas
• introducir herramientas avanzadas de representación de lenguajes

Temario de Aulas

1. Introducción
   1. Conceptos básicos
   2. Lenguajes y Operaciones fundamentales
   3. Gramáticas generativas
   4. Lenguaje generado por una gramática
   5. Clasificación de gramáticas

2. Autómatas finitos y expresiones regulares
   1. Autómatas finitos deterministas
      1. Representación de un AFD
      2. Lenguaje reconocido por un AFD
   2. Autómatas finitos no deterministas
      1. Representación de un AFND
      2. Lenguaje reconocido por un AFND
      3. Equivalencia entre AFD y AFND
   3. AFNDs con transiciones nulas
      1. Equivalencia entre AFND con y sin transiciones nulas
   4. Expresiones regulares
   5. Autómatas finitos con salida
      1. Máquinas de Moore
      2. Máquinas de Mealy
      3. Equivalencia entre máquinas de Moore y de Mealy

3. Lenguajes Regulares
   1. Lema de Bombeo y sus aplicaciones
   2. Operaciones cerradas sobre lenguajes regulares
   3. Algoritmos de decisión para lenguajes regulares
   4. Minimización de autómatas finitos

4. Gramáticas Libres de Contexto
   1. Introducción
   2. Simplificación de gramáticas libres de contexto
      1. Símbolos inútiles
      2. Producciones nulas
      3. Producciones unitarias
   3. Forma normal de Chomsky
   4. Forma normal de Greibach

5. Autómatas con Pila
   1. Introducción
   2. Autómatas con pila no deterministas
      1. Movimientos
      2. Descripción instantanea
   3. Autómatas con pila deterministas
   4. Lenguaje aceptado por un autómata con pila
   5. Autómatas con pila y lenguajes libres de contexto

6. Propiedades de los lenguajes libres de contexto
   1. Lema de Bombeo para lenguajes libres de contexto
   2. Operaciones cerradas de los lenguajes libres de contexto
   3. Algoritmo de decisión para lenguajes libres de contexto
   4. Pertenencia al lenguaje y algoritmos

7. Máquinas de Turing
   1. Introducción
   2. Definición del modelo de máquina de Turing
   3. Restricciones a las máquinas de Turing
   4. Descripción instantanea
   5. Lenguaje aceptado por una máquina de Turing
   6. Modificaciones de la máquina de Turing

Temario de Laboratorio

Se presenta en las clases prácticas.

Referencias bibliográficas

Básicas

1. P. Isasi, P. Martínez, D. Borrajo. Lenguajes, Gramáticas y Autómatas. Un enfoque práctico. Addison-Wesley, ISBN 84-7829014-1, 1997-2001.
2. M. Alfonseca, J. Sancho, M. Martínez Orga. Teoría de Lenguajes, Gramáticas y Autómatas. Promo-soft Publicaciones, R.A.E.C. ISBN 84-605-6092-9, 1997.

Complementarias

Método docente

Se imparte la signatura en clases de teoría con transparencias o portátil con cañón y pizarra con una participación activa del alumnado.

Sistema de evaluación

1. Hay que aprobar tanto la parte de Teoría como la parte de Prácticas.
2. La evaluación de la Teoría constará de un examen final.
3. Para aprobar la parte de Prácticas será requisito indispensable entregar en los plazos correspondientes los trabajos requeridos.
4. La nota final se calcula ponderando un 70% la Teoría y un 30% las Prácticas.