Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 2013) 2023-1

Cuarto Semestre, Autómatas y Lenguajes Formales

Grupo 7050, 42 lugares. 34 alumnos.
Profesor Araceli Liliana Reyes Cabello lu mi 18 a 19:30
Ayudante Rafael Reyes Sánchez ma ju 19:30 a 20:30

 

El objetivo del 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.

Se 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.

La estrategía de aprendizaje será por medio de Aprendizaje Basado en Proyectos, por lo que antes de clase se dejará material para revisar sobre conceptos, de tal manera que durante las clases síncronas con la profesora se revisen dudas y se resuelvan ejercicios. Las sesiones de ayudantía se utilizarán para evaluaciones, ejercicios y trabajar sobre proyectos, así como todas dudas que surjan de las clases.
Para las sesiones síncronas se utilizará la plataforma meet de google con los siguientes datos de conección y la primer reunión será el próximo lunes 15 de agosto a las 18 hrs.
meet.google.com/etu-vxqc-emm

Para las actividades asíncronas y publicación de materiales utilizaremos Google Classroom. Deberán envíar un correo desde tu cuenta institucional con asunto INSCRIPCIÓN al correo

rreyes@ciencias.unam.mx
para solicitar su acceso a Classroom, deberán incluir nombre completo y número de cuenta.

Temario

1. Introducción
a. Cadenas y lenguajes
b. Definiciones inductivas
c. Inducción estructural
2. Lenguajes regulares
a. Expresiones regulares
b. Autómatas finitos (AFD, AFN)
c. Teorema de Kleene
d. Teorema de Myhill-Nerode
3. Lenguajes libres de contexto
a. Gramáticas y formas normales
b. Autómatas de pila
c. Ambigüedad
d. Algoritmos y procedimientos de decisión
4. Máquinas de Turing
a. Definición y diseño de máquinas de Turing
b. Lenguajes recursivos y recursivamente enumerables

Referencias


1. James A. Anderson. Automata Theory with Modern Applications. Cambridge University Press 2006.
2. Martin Davis, Ron Sigal, Elaine J. Weyuker. Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science. Academic Press, 1983.
3. Maribel Fernández, Models of Computation, An Introduction to Computability Theory. Springer 2009.
4. J.E. Hopcroft, R. Motwani y J. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd. Edition, Pearson, 2006.
5. John Martin. Introduction to Languages and the Theory of Computation, 4th Edition, McGraw-Hill 2010.

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.