Título en inglés: Introduction to languages and the theory of computation Traducción: Jorge Luis Blanco y Correa Magallanes Incluye: Referencias.- Bibliografía.- Indice de notación.- Indice PARTE I. NOTACIÓN Y TÉCNICAS MATEMÁTICAS. 1. Objetos matemáticos básicos. 2. Introducción matemática y definiciones recursivas. PARTE II. LENGUAJES REGULARES Y AUTÓMATAS FINITOS. 3. Expresiones regulares y autómatas finitos. 4. No determinismo y el teorema de Kleene. 5. Lenguajes regulares y no regulares. PARTE III. LENGUAJES DE CONTEXTO LIBRE Y AUTÓMATAS FINITOS CON PILAS. 6. Gramáticas de contexto libre. 7. Autómatas con pila. 8. Lenguajes de contexto libre y lenguajes que no son de contexto libre. PARTE IV MÁQUINAS DE TURING Y SUS LENGUAJES. 9. Máquinas de Turing. 10. Lenguajes enumerables recursivamente. PARTE V. PROBLEMAS INSOLUBLES Y FUNCIONES COMPUTABLES. 11. Problemas insolubles. 12. Funciones computables. PARTE VI. INTRODUCCIÓN A LA COMPLEJIDAD COMPUTACIONAL. 13. Medición y clasificación de la complejidad. 14. Problemas tratables e intratables.
Resumen
Es un tratado de la teoría de la computación con énfasis en los lenguajes formales, autómatas y modelos abstractos de computación y de computabilidad; también incluye una introducción a la complejidad computacional y a los problemas NP completos. Entre las características fundamentales de esta excelente obra, destacan las siguientes: · La presentación de los conceptos fundamentales se vincula con situaciones del mundo real de la computación. · Está diseñada para ser accesible, tanto para quien posee una formación básica en matemáticas discretas, como para quien carece de la misma, ya que las explicaciones son detalladas y están muy bien organizadas. · Contiene una gran cantidad y variedad de problemas y ejercicios, con diversos grados de dificultad. · Realiza una presentación contextualizada y gradual de las herramientas matemáticas necesarias para el desarrollo de la comprensión de los lenguajes formales. · El sitio web http://highered.mcgraw-hill.com/sites/0072322004 contiene recursos didácticos adicionales para un aprendizaje óptimo.
