View source for Introduction to Automata Theory, Languages, and Computation

{{short description|1979 computer science textbook}}
{{No footnotes|date=December 2011}}

{{Infobox book
| name         = Introduction to Automata Theory, Languages, and Computation
| title_orig   = 
| translator   = 
| image        = Introduction to Automata Theory, Languages, and Computation.jpg
| caption= Cover of the Cinderella Book (1979 edition)
| author       = [[John Hopcroft]] and [[Jeffrey Ullman]]
| illustrator  = 
| cover_artist = 
| country      = USA
| language     = English
| series       = 
| subject      = [[Computer science]]
| publisher    = [[Addison-Wesley]]
| pub_date     = 1979
| media_type   = Print 
| pages        = 
| isbn =  0-201-02988-X
| dewey= 629.8/312
| congress= QA267 .H56
| oclc         = 4549363| followed_by  = 
}}

'''''Introduction to Automata Theory, Languages, and Computation''''' is an influential [[computer science]] textbook by [[John Hopcroft]] and [[Jeffrey Ullman]] on [[formal language]]s and the [[theory of computation]].  [[Rajeev Motwani]] contributed to later editions beginning in 2000.

== Nickname ==
The [[Jargon File]] 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."<ref>{{cite web|url=http://www.catb.org/~esr/jargon/html/C/Cinderella-Book.html|title=Cinderella Book|access-date=July 22, 2020}}</ref>

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

*{{cite book
  | last1 = Hopcroft
  | first1 = John E. 
  | last2 = Ullman
  | first2 = Jeffrey D.
  | title = Formal Languages and Their Relation to Automata
  | url = https://archive.org/details/formallanguagest00hopc
  | url-access = registration
  | publisher = Addison-Wesley
  | year = 1968
| isbn = 9780201029833 
 }}
*{{Hopcraft and Ullman 1979|author-link=no|archive-link=no}}
*{{cite book
  | last1 = Hopcroft
  | first1 = John E.
  | last2 = Motwani
  | first2 = Rajeev 
  | last3 = Ullman
  | first3 = Jeffrey D.
  | title = Introduction to Automata Theory, Languages, and Computation
  | publisher = Addison-Wesley
  | year = 2000
  | edition = 2nd
  | isbn = 81-7808-347-7
}}
*{{Hopcroft, Motwani, and Ullman 2006|author-link=no}}
*{{cite book
  | last1 = Hopcroft
  | first1 = John E.
  | last2 = Motwani
  | first2 = Rajeev 
  | last3 = Ullman
  | first3 = Jeffrey D.
  | title = Introduction to Automata Theory, Languages, and Computation
  | publisher = Pearson
  | year = 2013
  | edition = New International
  | isbn = 978-1292039053
}}

[[File:Hopcroft-ullman-old.jpg|thumb|left|''Formal Languages and Their Relation to Automata'' appeared in 1968, with an inornate cover.]]

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 [[Jeffrey Shallit|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 positively 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.<ref>{{Cite web |title=CiteSeerX Most Cited Computer Science Citations |url=http://citeseerx.ist.psu.edu/stats/citations |url-status=dead |archive-url=https://web.archive.org/web/20220921215315/https://citeseerx.ist.psu.edu/stats/citations |archive-date=Sep 21, 2022 |access-date=May 20, 2009}}</ref>

==See also==
*''[[Introduction to the Theory of Computation]]'' by [[Michael Sipser]], another standard textbook in the field 
*[http://infolab.stanford.edu/~ullman/ialcsols/sols.html Solutions to Selected Exercises], Stanford University

==References==
{{Reflist}}

==External links==
* Entry [http://catb.org/~esr/jargon/html/C/Cinderella-Book.html "Cinderella book".] In: [[The Jargon file]] (version 4.4.7, December 29, 2003).
* {{cite journal| last = Hopcroft
  | first = John E. 
  | title=The emergence of computer science - A citation classic commentary on 'Formal Languages and Their Relation to Automata'
  | url=http://garfield.library.upenn.edu/classics1989/classics1989.html
  | journal=[[Current Contents|Current Contents Engineering, Technology, and Applied Sciences]]
  | volume=31
  | pages=12
  | year=1989
}} [http://garfield.library.upenn.edu/classics1989/A1989AF70300001.pdf available online (pdf)]
*{{cite book
  | last = Shallit
  | first = Jeffrey O.
  | author-link = Jeffrey Shallit
  | title = A Second Course in Formal Languages and Automata Theory
  | publisher = Cambridge University Press
  | year = 2008
  | page = ix
  | isbn = 978-0-521-86572-2
}}
*{{cite web | title=Introduction to Automata Theory, Languages, and Computation - Home page |website=Stanford University | url=http://infolab.stanford.edu/~ullman/ialc.html | archive-url=https://web.archive.org/web/20230607132150/http://infolab.stanford.edu/~ullman/ialc.html | archive-date=7 June 2023 | url-status=live}}
* {{cite web| title=Introduction to Automata Theory, Languages, and Computation; 1st edition | url=https://archive.org/details/trent_0116301269779}} — accessible only to Internet Archive patrons with print disabilities

[[Category:Computer science textbooks]]
[[Category:Formal languages]]
[[Category:Automata (computation)]]
[[Category:1968 non-fiction books]]
[[Category:1979 non-fiction books]]
[[Category:2000 non-fiction books]]
[[Category:2006 non-fiction books]]
[[Category:2016 non-fiction books]]