Introducción a la teoría de autómatas, lenguajes y computación es un influyente libro de texto de informática escrito por John Hopcroft y Jeffrey Ullman sobre lenguajes formales y teoría de la computación . Rajeev Motwani contribuyó a ediciones posteriores a partir de 2000.
El apodo del libro, Cinderella Book (Libro de Cenicienta ), se registra así: "Se llama así porque la portada muestra a una niña (supuestamente Cenicienta) sentada 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". [1]
El precursor de este libro apareció bajo el título Lenguajes formales y su relación con los autómatas en 1968. Al constituir una base tanto para la creación de cursos sobre el tema como para investigaciones posteriores, ese libro dio forma al campo de la teoría de autómatas durante más de una década, cf. (Hopcroft 1989).
La primera edición de Introducción a la teoría de autómatas, lenguajes y computación 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 autómatas , mientras que se eliminaron grandes partes de la teoría más avanzada. Si bien esto hace que la segunda y la tercera ediciones sean más accesibles para principiantes, las hace menos adecuadas para cursos más avanzados. El nuevo sesgo que se aleja de la teoría no es visto positivamente por todos: 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 Formal Languages and Their Relation to Automata . Se publicó en 1968 y se hace referencia a él en la introducción de la edición de 1979. En una nota histórica personal sobre el libro de 1968, Hopcroft afirma: "Tal vez el éxito del libro se debió a nuestros esfuerzos por presentar la esencia de cada prueba antes de dar la prueba en sí" (Hopcroft 1989). En comparación con el libro precursor, la edición de 1979 se amplió y el material se reelaboró 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 sobre la edición revisada de 1979: "Parece que nuestros intentos de reducir el nivel de nuestra presentación para el beneficio de los estudiantes incluyendo más detalles y explicaciones tuvieron un efecto adverso en el profesorado, que luego tuvo que examinar cuidadosamente el material agregado para delinear y preparar sus conferencias" (Hopcroft 1989).
Aún así, la edición más citada del libro es aparentemente la 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. [2]