Introducción a la teoría de autómatas, lenguajes y computación / John E. Hopcroft y Jeffrey D. Ullman

Contenido -- 1. Preliminares -- 2. Autómatas finitos y expresiones regulares -- 3. Propiedades de los conjunto regulares -- 4. Gramáticas libres de contexto -- 5. Autómatas de apilamiento -- 6. Propiedades de los lenguajes libres de contexto -- 7. Maquinas de Turing -- 8. Irresolubilidad -- 9. La jerarquía de Chomsky -- 10 Lenguajes determinísticos libres de contexto -- 11. Propiedades de cerradura de familias de lenguaje -- 12. Teoría de complejidad computacional -- 13. Problemas no tratables -- 14. Características principales de otras clases de lenguaje -- Bibliografía -- Índice

Por muchos años, los autores de este texto, vieron que era necesario producir un libro que abarcara el material sobre lenguajes formales, teoría de autómatas y complejidad computacional. Al escribir esta obra sobre la materia, encontramos que el campo se ha extendido en tantas direcciones nuevas que tratar el tema de manera total y uniforme ha resultado imposible. Resultó drástico editar el material. Se han seleccionando sólo los temas centrales del desarrollo teórico del campo o sólo los que tienen importancia en las aplicaciones de ingeniería.