Lenguajes formales y teoría de la computación

John C. Martin realizó sus estudios en la Rice University, donde obtuvo en 1966 la licenciatura en matemáticas y en 1971 el doctorado. Impartió cátedra durante dos años en la University of Hawai en Honolulu, antes de integrarse a la North Dakota State University, donde es profesor asociado de ciencias de la computación. Descripción 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. Tabla de Contenido 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. Referencias. Bibliografía. ??ndice.