Principal

El propósito de este curso es desarrollar la teoría clásica de la computación mediante la descripción y estudio de ciertos modelos matemáticos de la noción de cómputo. Los conceptos fundamentales son tres: lenguaje, gramática y autómata, los cuales  estudiaremos con un enfoque riguroso y en ciertos casos con mayor detalle que en un curso de licenciatra. El objetivo general del curso es estudiar a profundidad distintas clases de lenguajes, gramáticas y autómatas haciendo énfasis en los conceptos abstractos de cómputo y poder computacional pero también mencionando algunas aplicaciones
Si el tiempo lo permite estudiaremos otros lenguajes formales de importancia como el cálculo lambda y las funciones recursivas.

Temario: 

  1. Introducción: cadenas y lenguajes, definiciones inductivas, inducción estructural.
  2. Lenguajes regulares: autómatas finitos, expresiones regulares.
  3. Lenguajes libres de contexto: gramáticas, autómatas de pila.
  4. Máquinas de Turing: lenguajes recursivos y recursivamente enumerables, formalismos equivalentes (programas WHILE y GOTO)
  5.  Otros lenguajes formales: cálculo lambda sin tipos, funciones recursivas.


Avisos recientes

  • Guia de ejercicios para el segundo parcial La siguiente lista de ejercicios se refieren al cuarto capítulo de la cuarta edición en inglés del libro de Martin, y sirven de guía para el segundo parcial. En cualquier ...
    Posted by Favio Miranda
  • Temas para el examen del lunes 26 El examen constará exclusivamente de los siguientes temas:1. Diseño de gramáticas libres de contexto.2. Derivaciones  y árboles de derivación.3. Transformación a forma normal de Chomsky4.  Ambigüedad ...
    Posted by Favio Miranda
Showing posts 1 - 2 of 12. View more »
Autómatas y Lenguajes Formales
Maestría en Ciencia e Ingeniería de la Computación UNAM.

Prof. Dr. Favio Ezequiel Miranda Perea
Ayud. M. en C. Pilar Selene Linares Arévalo

Horario: Lunes y miércoles, 1630 a 1800hrs.
Salón: 304, edificio anexo al IIMAS


Sesiones de Asesoría:
Habrá sesiones de asesoría, los lunes y miércoles entre las 15:00 y 16:30 hrs previa confirmación. Para confirmar la reunión, favor de enviar un correo (con al menos 24 hrs de anticipación) a selene_linares@ciencias.unam.mx indicando el día y la hora en la que desean asistir. Las reuniones se realizarán en el cub 20 del departamento de matemáticas de la Facultad de Ciencias.  


Prerrequisitos:
   
   Se suponen conocidos los siguientes puntos:
  • Nociones elementales de la teoría de conjuntos: pertenencia y contención, operaciones con conjuntos, funciones
  • Relaciones binarias: propiedades y operaciones
  • Números naturales:  definición, principios de inducción.