Introducción a la teoría, los lenguajes y la computación de autómatas

Introducción a la teoría, los lenguajes y la computación de los autómatas es un influyente libro de texto de informática escrito por John Hopcroft y Jeffrey Ullman sobre lenguajes formales y la teoría de la computación. Rajeev Motwani contribuyó a ediciones posteriores a partir de 2000.

Apodo

The Jargon File registra el apodo del libro, Libro de Cenicienta, así: "Se llama así porque la portada representa a una niña (supuestamente Cenicienta) sentado frente a un dispositivo de Rube Goldberg y sosteniendo una cuerda que sale de él. En la contraportada, el dispositivo está en ruinas después de que ella (inevitablemente) haya tirado de la cuerda."

Historial de edición y recepción

El precursor de este libro apareció bajo el título Lenguajes formales y su relación con los autómatas en 1968. Sirviendo de base tanto para la creación de cursos sobre el tema, como así como para futuras investigaciones, ese libro dio forma al campo de la teoría de los autómatas durante más de una década, cf. (Hopcroft 1989).

• Hopcroft, John E.; Ullman, Jeffrey D. (1968). Lenguas formales y su Relación con Automata. Addison-Wesley. ISBN 9780201029833.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a Automata Teoría, idiomas y computación (1a edición). Addison-Wesley. ISBN 0-201-02988-X.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2000). Introducción a Automata Teoría, idiomas y computación (2a edición). Addison-Wesley. ISBN 81-7808-347-7.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introducción a Automata Teoría, idiomas y computación (3a edición). Addison-Wesley. ISBN 0-321-45536-3.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introducción a Automata Teoría, idiomas y computación (3a edición). Pearson. ISBN 978-1292039053.

La primera edición de Introducción a la teoría, los lenguajes y la computación de autómatas se publicó en 1979, la segunda edición en noviembre de 2000 y la tercera edición apareció en febrero de 2006. Desde la segunda edición, Rajeev Motwani se ha unido a Hopcroft y Ullman como tercer autor. A partir de la segunda edición, el libro presenta una cobertura ampliada de ejemplos en los que se aplica la teoría de los autómatas, mientras que se eliminaron gran parte de la teoría más avanzada. Si bien esto hace que la segunda y tercera edición sean más accesibles para los principiantes, las hace menos adecuadas para cursos más avanzados. No todos ven positivamente el nuevo sesgo que se aleja de la teoría: como Shallit cita a un profesor, "han eliminado todas las partes buenas". (Shallit 2008).

La primera edición, a su vez, constituyó una revisión importante de un libro de texto anterior también escrito por Hopcroft y Ullman, titulado Lenguajes formales y su relación con los autómatas. Fue publicado en 1968 y se menciona en la introducción de la edición de 1979. En una nota histórica personal sobre el libro de 1968, Hopcroft afirma: "Quizás el éxito del libro se debió a nuestros esfuerzos por presentar la esencia de cada prueba antes de darla". (Hopcroft 1989). En comparación con el libro precursor, la edición de 1979 fue ampliada y el material fue reelaborado para hacerlo más accesible a los estudiantes, cf. (Hopcroft 1989). Esta orientación hacia la comprensibilidad a costa de la concisión no fue vista positivamente por todos. Como informa Hopcroft sobre los comentarios recibidos sobre la edición revisada de 1979: "Parece que nuestros intentos de bajar el nivel de nuestra presentación en beneficio de los estudiantes incluyendo más detalles y explicaciones tuvieron un efecto adverso en los profesores, quienes luego tuvieron que examinar el material agregado para delinear y preparar sus conferencias" (Hopcroft 1989).

Aun así, la edición más citada del libro es aparentemente la edición de 1979: según el sitio web CiteSeerX, Más de 3000 artículos científicos disponibles gratuitamente en línea citan esta edición del libro.