Teoria de la computación

Facultad de Matemáticas
Notas de Curso de la Asignatura “Teoría de la Computación”

Impartida a los alumnos del tercer semestre de la Licenciatura en Ciencias de la Computación, Unidad Tizimín

Elaborado por: M.C. Cinhtia Maribel González Segura M.C. Michel García García Tizimín, Yucatán. Diciembre de 2006

Contenido
Carta descriptiva...............................................................................3 Contenido del programa.....................................................................4 Material de las Unidades ....................................................................5 Unidad 1 ...............................................................................................5 Unidad 2.............................................................................................16 Unidad 3 .............................................................................................35 Unidad 4 ...........................................................................................141 Unidad 5 ...........................................................................................151Bibliografía........................................................................................160 Ejercicios.......................................................................................161 Unidades 1 y 2 ..................................................................................161 Unidad 3 ...........................................................................................162 Unidad 4...........................................................................................163 Unidad 5 ...........................................................................................164 Dinámicas de Repaso .....................................................................165 Tareas............................................................................................166 Unidades 1 y 2..................................................................................166 Unidad 3 ...........................................................................................167 Unidad 4 ...........................................................................................169 Unidad 5 ...........................................................................................170 Bibliografía....................................................................................172 Anexos...........................................................................................173 Programa de la asignatura.................................................................173

Elaboró: M.C. Cinhtia M. González Segura.

i

Carta descriptiva
La asignatura Teoría de la Computación se imparte en el tercersemestre de la Licenciatura en Ciencias de la Computación, plan 2004. El contenido de esta asignatura coincide en un porcentaje mayor al 90% con Teoría de Lenguajes y Autómatas del plan anterior (1997). El presente material está elaborado con base en los contenidos dicha asignatura. El material que aquí se presenta fue elaborado por la M.C. Cinhtia M. González Segura para el semestre Agosto 2006 –Enero 2007, y se distribuyó a los alumnos en su momento, durante el curso. En primer lugar se incluye el programa del curso, después se presentan los recursos didácticos empleados, en su mayoría diapositivas que sirven como guía en la exposición de las clases, posteriormente se incluyen notas del curso que acompañan y complementan a las primeras, y al final, se incluye el manual de operaciones paraun uso adecuado del material.

Datos de la Asignatura Clave: MT-13 Nombre: Teoría de la Computación Plan: Licenciatura en Ciencias de la Computación (LCC), Ingeniería de Software (IS), Ingeniería en Computación (IC) Semestre: Tercero en LCC, IS y Cuarto en I.C. Créditos: 10 Hrs semanales: 4.5 Total de horas: 72 Requisitos previos: Matemáticas Discretas

Elaboró: M.C. Cinhtia M. González...