next_inactive up previous


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

24 de febrero de 2006

Datos administrativos de la Universidad

Asignatura

Código de la materia 106012224
Nombre de la materia Teoría de Autómatas y de Lenguajes Formales
Centro/Titulación Escuela Superior de Ingeniería Informática
Ingeniero Técnico en Informática de Gestión
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 segundo cuatrimestre
Departamento Informática
Área de conocimiento Área de Lenguajes y Sistemas Informáticos

Horario

Lunes Martes Jueves
9-10 TALF(A) 22
10-11 TALF(A1) 10
11-12 TALF(A2) 10
12-13 TALF(A) 22 TALF(B7) 10
13-14 TALF(A) 22
14-15
15-16
16-17 TALF(B)/TALF(A3) 22/10 TALF(B) 22
17-18 TALF(B) 22
18-19 TALF(AB4) 40
19-20 TALF(B5) 40
20-21 TALF(B6) 40

Datos de los exámenes

Convocatoria Fecha Hora Aula
Junio 06.06.06 10:00 Aula Magna
Septiembre 11.09.06 16:00 Aula Magna
Diciembre por determinar

Tribunal extraordinario

Presidente Prof. Celso Campos Basto
Secretario Prof. Dra. Reyes Pavón Rial
Vocal Prof. Dr. Juan Francisco Gálvez Gálvez
Suplente Prof. Alma Gómez Rodríguez

Profesorado de la materia

Profesor Desp. Crd. Tutorías
Dr. Arno Formella 309 9 (Teoría) mira Web de Profesores
Dra. Eva Cernadas García 309 3 (Prácticas) mira Web de Profesores
José Luis Carnero Sobrino 308 7.5 (Prácticas) mira Web de Profesores

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:

Temario de Aulas

  1. Introducción
  2. Conceptos básicos
    1. Alfabetos
    2. Palabras
    3. Lenguajes
    4. Producciones y Derivaciones
    5. Relaciones de equivalencia
    6. Relación de equivalencia de lenguajes
  3. Gramáticas generativas
    1. Ejemplos
    2. Abreviación de Backus
    3. Árbol de derivación
    4. Jerarquia de Chomsky
    5. Equivalencia y ambigüedad
  4. Autómatas finitos
    1. Autómatas finitos deterministas (AFD)
    2. Autómatas finitos no-deterministas (AFND)
    3. Equivalencia entre AFD y AFND
    4. Autómatas finitos no-deterministas con transiciones $ \epsilon$ (AFND-$ \epsilon$)
    5. Equivalencia entre AFND y AFND-$ \epsilon$
    6. Existencia de autómatas finitos mínimos
    7. Ejemplos de uso del teorema de Myhill y Nerode
    8. Algoritmo de minimización
  5. Expresiones regulares
    1. Síntaxis y semántica
    2. Equivalencia entre autómatas finitos y expresiones regulares
    3. Abreviaciones para el uso de expresiones regulares
    4. Símbolos y meta-símbolos
  6. Lenguajes Regulares
    1. Equivalencia entre lenguajes lineales por la derecha y autómatas finitos
    2. Equivalencia entre gramáticas lineales por la derecha y lineales por la izquierda
    3. Lema de bombeo
  7. Propiedades y algoritmos de decisión para lenguajes regulares
    1. Propiedades de lenguajes regulares
    2. Algoritmos de decisión de lenguages regulares
  8. Lenguajes libres de contexto
    1. Forma Normal de Chomsky
    2. Forma Normal de Greibach
    3. Lema de bombeo para lenguajes libres de contexto
  9. Autómatas finitos con pila
    1. Motivación
    2. Autómatas finitos con pila no-deterministas (AFPND)
    3. Equivalencia entre AFPNDs aceptando con pila vacía y aceptando en estado final
    4. Equivalencia entre AFPNDs y gramáticas libres de contexto
    5. Autómatas finitos con pila deterministas (AFPD)
  10. Propiedades y algoritmos de decisión para lenguajes libres de contexto
    1. Propiedades de lenguajes libre de contexto
    2. Algoritmos de decisión de lenguages libres de contexto
  11. Maquinas de Turing (MT)
  12. Resumen

Temario de Laboratorio

En las prácticas se verá el uso de lenguajes formales, de autómatas y de expresiones regulares en herramientas de uso en el ámbito de la informática (por ejmeplo: búsquedas en el sistema operativo, búsquedas y reemplacimientos en editores de texto, especificación formal de contenidos de ficheros, etc.). Además se implementará algunos de los algoritmos básicos que se estudia en la teoría.

Referencias bibliográficas

Básicas

  1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación. Segunda edición, Addison-Wesley, 2002 (Signatura: OUR 681.34/46).
  2. Pedro Isasi, Paloma Martínez, Daniel Borrajo. Lenguajes, Gramáticas y Autómatas. Un enfoque práctico. Addison-Wesley, ISBN 84-7829014-1, 1997-2001 (Signatura OUR 681.34/13).
  3. Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga. Teoría de Lenguajes, Gramáticas y Autómatas. Universidad y Cultura, 1990 (Signatura: OUR 681.34/31).

Método docente

Se imparte la teoría de la asignatura con clases mayestrales desarrollando el temario por pizarra animando a los estudiantes de participar. Las prácticas se realizan con herramientas de programación a gusto del alumno y con herramientas comunes en un entorno informático.

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. La evaluación de las Prácticas constará en una evaluación continua durante las clases en el laboratorio.
  4. La nota final se calcula ponderando un 70% la Teoría y un 30% las Prácticas.

(Una lógica consecuencia de este método es: si alguien logra solamente un 0 en las prácticas (por ejemplo, porque no participa) puede alcanzar como mucho un 7 en la nota final y necesita por lo menos un 7 en el examen de teoría para aprobar la asignatura.)

next_inactive up previous
© 2006, Dr. Arno Formella, Universidad de Vigo, Departamento de Informática