Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions beginning in 2000. The records the book's nickname, Cinderella Book, thusly: "So called because the cover depicts a girl (putatively Cinderella) sitting in front of a Rube Goldberg device and holding a rope coming out of it. On the back cover, the device is in shambles after she has (inevitably) pulled on the rope." The forerunner of this book appeared under the title Formal Languages and Their Relation to Automata in 1968. Forming a basis both for the creation of courses on the topic, as well as for further research, that book shaped the field of automata theory for over a decade, cf. (Hopcroft 1989). The first edition of Introduction to Automata Theory, Languages, and Computation was published in 1979, the second edition in November 2000, and the third edition appeared in February 2006. Since the second edition, Rajeev Motwani has joined Hopcroft and Ullman as the third author. Starting with the second edition, the book features extended coverage of examples where automata theory is applied, whereas large parts of more advanced theory were taken out. While this makes the second and third editions more accessible to beginners, it makes it less suited for more advanced courses. The new bias away from theory is not seen positively by all: As Shallit quotes one professor, "they have removed all good parts." (Shallit 2008). The first edition in turn constituted a major revision of a previous textbook also written by Hopcroft and Ullman, entitled Formal Languages and Their Relation to Automata. It was published in 1968 and is referred to in the introduction of the 1979 edition. In a personal historical note regarding the 1968 book, Hopcroft states: "Perhaps the success of the book came from our efforts to present the essence of each proof before actually giving the proof" (Hopcroft 1989).