Introduction to Automata Theory, Languages, and Computation
Encyclopedia
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
.
) on the cover with a Rube Goldberg machine
.
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 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).
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
textbook by John Hopcroft
John Hopcroft
John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
and Jeffrey Ullman
Jeffrey Ullman
Jeffrey David Ullman is a renowned computer scientist. His textbooks on compilers , theory of computation , data structures, and databases are regarded as standards in their fields.-Early life & Career:Ullman received a Bachelor of Science degree in Engineering...
on formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s and the theory of computation
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
.
Nickname
Among experts also known as the Cinderella Book. This nickname is derived from a girl (putatively CinderellaCinderella
"Cinderella; or, The Little Glass Slipper" is a folk tale embodying a myth-element of unjust oppression/triumphant reward. Thousands of variants are known throughout the world. The title character is a young woman living in unfortunate circumstances that are suddenly changed to remarkable fortune...
) on the cover with a Rube Goldberg machine
Rube Goldberg machine
A Rube Goldberg machine, contraption, device, or apparatus is a deliberately over-engineered or overdone machine that performs a very simple task in a very complex fashion, usually including a chain reaction...
.
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 theoryAutomata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
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
Rajeev Motwani
Rajeev Motwani was a professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was an early advisor and supporter of companies including Google and PayPal, and a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in...
has joined Hopcroft and Ullman as third author.
Starting with the second edition, the book features extended coverage of examples where automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
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
Jeffrey Shallit
Jeffrey Outlaw Shallit is a computer scientist, number theorist, a noted advocate for civil liberties on the Internet, and a noted critic of intelligent design. He is married to Anna Lubiw, also a computer scientist....
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
CiteSeerX
CiteSeerX is a public search engine and digital library and repository for scientific and academic papers with a focus on computer and information science. It is loosely based on the previous CiteSeer search engine and digital library and is built with a new open source infrastructure, SeerSuite,...
,
over 3000 scientific papers freely available online cite this edition of the book (CiteSeerX, 2009).
See also
- Introduction to the Theory of ComputationIntroduction to the Theory of ComputationIntroduction to the Theory of Computation is a standard textbook in theoretical computer science, written by Michael Sipser.-See also:...
by Michael SipserMichael SipserMichael Fredric Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. He received his Ph.D. in 1980 from the University of California, Berkeley under the direction of Manuel Blum....
, another standard textbook in the field - List of important publications in theoretical computer science