Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation, among experts also known as the Cinderella Book, is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. 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, tha... more

Introduction to Automata Theory, Languages, and Computation, among experts also known as the Cinderella Book, is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. 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 nickname "Cinderella book" is derived from a girl (putatively Cinderella) on the cover with a Rube Goldberg machine. 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 third author. Starting with the second edition, the book features extended... less