Samiksha Jaiswal (Editor)

Introduction to Automata Theory, Languages, and Computation

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Country
  
USA

Media type
  
Print

OCLC
  
4549363

Originally published
  
1979

Subject
  
Computer Science

Genre
  
Textbook

Publication date
  
1979

ISBN
  
0-201-02988-X

Dewey Decimal
  
629.8/312

Original language
  
English

Publisher
  
Addison-Wesley

Introduction to Automata Theory, Languages, and Computation t0gstaticcomimagesqtbnANd9GcQLlFsaGjAmclM7RV

Authors
  
Jeffrey Ullman, John Hopcroft

Similar
  
Jeffrey Ullman books, Textbook books, Theory of computation books

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.

Contents

Nickname

Among experts also known as the Cinderella Book. This nickname is derived from a girl (putatively Cinderella) on the cover with a Rube Goldberg machine.

Edition History and Reception

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).

  • Hopcroft, John E.; Ullman, Jeffrey D. (1968). Formal Languages and Their Relation to Automata. Addison-Wesley. 
  • Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 81-7808-347-7. 
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2000). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Addison-Wesley. ISBN 81-7808-347-7. 
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. ISBN 81-7808-347-7. 
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson. ISBN 1292039051. 
  • 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 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 positive 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). Compared with the forerunner book, the 1979 edition was expanded, and the material was reworked to make it more accessible to students, cf. (Hopcroft 1989). This gearing towards understandability at the price of succinctness was not seen positive by all. As Hopcroft reports on feedback to the overhauled 1979 edition: "It seems that our attempts to lower the level of our presentation for the benefit of students by including more detail and explanations had an adverse effect on the faculty, who then had to sift through the added material to outline and prepare their lectures" (Hopcroft 1989).

    Still, the most cited edition of the book is apparently the 1979 edition: According to the website CiteSeerX, over 3000 scientific papers freely available online cite this edition of the book (CiteSeerX, 2009).

    References

    Introduction to Automata Theory, Languages, and Computation Wikipedia