''Introduction to Automata Theory, Languages, and Computation'' is an influential

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

textbook by

John Hopcroft John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is the IBM P ...

and

Jeffrey Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the d ...

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sym ...

s and the

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how algorithmic efficiency, efficiently they can be solved or t ...

. Rajeev Motwani contributed to later editions beginning in 2000.

Nickname

The

Jargon File The Jargon File is a glossary and usage dictionary of slang used by computer programmers. The original Jargon File was a collection of terms from technical cultures such as the MIT AI Lab, the Stanford AI Lab (SAIL) and others of the old ARPANET ...

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 Reuben Garrett Lucius Goldberg (July 4, 1883 – December 7, 1970), known best as Rube Goldberg, was an American cartoonist, sculptor, author, engineer, and inventor. Goldberg is best known for his popular cartoons depicting complicated gadge ...

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

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 Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

for over a decade, cf. (Hopcroft 1989). * * * * * Hopcroft-ullman-old

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

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). 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 CiteSeerX (formerly called CiteSeer) is a public search engine and digital library for scientific and academic papers, primarily in the fields of computer and information science. CiteSeer's goal is to improve the dissemination and access of ac ...

, over 3000 scientific papers freely available online cite this edition of the book.

References

External links

* Entr

In:

The Jargon file The Jargon File is a glossary and usage dictionary of slang used by computer programmers. The original Jargon File was a collection of terms from technical cultures such as the MIT AI Lab, the Stanford AI Lab (SAIL) and others of the old ARPANET A ...

(version 4.4.7, December 29, 2003). *
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

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

Nickname

Edition history and reception

See also

References

External links