Introduction to automata theory, languages, and computation
by John E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwani · first published 1979
73% recommend27% neutral
Why HN recommends it
Proof-heavy treatment of automata, formal languages, and computability, with a good section linking state machines to regular expressions. Suits CS students wanting a durable theory text or groundwork before compilers.
Summarised by Claude from recommending comments
"This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with increased coverage of practical applications. This third edition offers students a less formal writing style while providing the most accessible coverage of automata theory available, solid treatment on constructing proofs, many figures and diagrams to help convey ideas, and sidebars to highlight related material. A new feature of this edition is Gradiance, a Web-based homework and assessment tool. Each chapter offer
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2008–2026Introduction to the theory of computation
Michael Sipser
Recommended by 66 · mentioned by 8966 recommend · 89 mention66 recommend · 8966 recommend
2008–2024Computational complexity
Christos H. Papadimitriou
Recommended by 7 · mentioned by 97 recommend · 9 mention7 recommend · 97 recommend
2008–2025Discrete Mathematics and Its Applications
Kenneth H. Rosen
Recommended by 14 · mentioned by 1914 recommend · 19 mention14 recommend · 1914 recommend
2011–2025Parsing Techniques
Dick Grune
Recommended by 16 · mentioned by 1916 recommend · 19 mention16 recommend · 1916 recommend
2008–2024Theory of computation
Michael Sipser
Recommended by 14 · mentioned by 1914 recommend · 19 mention14 recommend · 1914 recommend
2007–2026Compilers, principles, techniques, and tools
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
Recommended by 195 · mentioned by 659195 recommend · 659 mention195 recommend · 659195 recommend
2012–2026Computer science
J. Glenn Brookshear, Brookshear
Recommended by 8 · mentioned by 118 recommend · 11 mention8 recommend · 118 recommend
2013–2026Understanding Computation
Tom Stuart
Recommended by 13 · mentioned by 1713 recommend · 17 mention13 recommend · 1713 recommend
…list from that. Also, there are some works where you really can't go wrong. Some examples: - Structure and Interpretation of Computer Programs, Abelson and Sussman - Algorithms, Sedgewick, Wayne - Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman Lesser known, but incredibly fun books: - Purely Functional Data Structures, Chris Okasaki - The Reasoned Schemer, Friedman, Byrd, Kiselyov (or a good Prolog book). After…
on “Ask HN: How to best acquire theoretical computer science knowledge?” ↗Structure and Interpretation of Computer Programs (), Introduction to Automata Theory, Languages and Computation (Hopcroft Ullman), don knuth's art of computer programming, Tanenbaum's Modern Operating Systems, Compilers: Principles, Techniques, and Tools5 (Aho Sethi Ullman)
on “Ask HN: What are the most fundamental books on computer science?” ↗Hopcroft Ullman's Introduction to Automata Theory, Languages and Computation has good section on state machines and their connection to Regular Expressions
on “Finite State Machines in Forth (1995)” ↗One book that I would suggest to anyone is Introduction to Automata Theory, Languages, and Computation - HMU. It is very approachable and presents some very interesting topics (so you won't write a regex for matching HTML and will learn what P vs NP means). On a more practical side, I think that a must…
on “Must Read CS Books For Self Self-Taught Programmers” ↗…Calculus 4th ed. by Smith and Minton 2. Introduction to Linear Algebra (Gilbert Strang) 3. Introduction to Probability Theory (Hoel, Port, Stone) 4. Discrete Mathematics and its applications (Rosen) 5. Introduction to Automata Theory, Languages, and Computation (Hopcroft) 6. Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) It will take you at least a year if not two to work through all these in your spare time, but the advantage is that after…
on “Ask HN: Resources to learn math as a foundation for CS” ↗…importance. * “Introduction to the Theory of Computation”, by Michael Sipser. * I also recommend the “Elements of the Theory of Computation”, by Christos Papadimitriou. * Another good complement is “Introduction to Automata Theory, Languages and Computation”, by Hopcroft and Ullman. (Thanks, @reacweb, for the reminder.) * “Graph Theory”, by Reinhard Diestel. * If you feel you want to go deeper, and like a book which you cannot skip a single word, I…
on “Ask HN: What are the most fundamental books on computer science?” ↗…of computing concepts and programming practice. If you do want a traditional intro to CS theory, two books that cover that topic well are: "Introduction to the Theory of Computation" by Sipser, and "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Motwani, and Ullman. Three very good books that introduce algorithms are: "Introduction to Algorithms: A Creative Approach" by Manber, "The Algorithm Design Manual" by Skiena, and "Algorithms"…
on “Ask HN: I'm looking for a good book on the fundamentals of CS” ↗There is also The Cinderella Book by Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation.
on “Ask HN: Book recommendations for grammar as it relates to computing?” ↗The fundamental book to read would be "Introduction to Automata Theory, Languages, and Computation" ( http://www.amazon.com/Introduction-Automata-Theory-Languages...) Then proceed to Dragonbook. After finishing Dragonbook, you might like this Linkers and loaders (http://www.amazon.com/Linkers-Kaufmann-Software-Engineering-...)…
on “Ask YC: Good compiler books?” ↗If you are in the mood for something advanced, take a look at Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman. It has a good amount of proofs and a pretty strong focus on automata thought so that may not be your cup of tea. Hopcroft won the Turing award in 1986 so he knows what…
on “Ask HN: Good books on computational complexity?” ↗…+ Data Structures = Programs by Wirth (worth its weight in gold if you can get past the Pascal syntax) OS -> Operating System Concepts by Silberschatz et al (The dinosaur book) CS Theory -> Introduction to Automata Theory, Languages, and Computation by Hopcroft, Ullman Programming Languages Theory -> Programming languages: design and implementation by Pratt et al Database Theory -> Database Design by Wiederhold Architecture -> Structured…
on “Must Read CS Books For Self Self-Taught Programmers” ↗…25 years ago, of course): "Compilers: Principles, Techniques, and Tools" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman (a.k.a the "Dragon Book") "The Art of Computer Programming" by Donald Knuth "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman An amazing book, despite the fact that the core thesis of the first edition, that we were on the verge of permanent world domination by RISC architectures,…
on “About 6.002x” ↗…book "Foundations of Computer Science" (http://i.stanford.edu/~ullman/focs.html) which is available online provides an excellent introduction to automata theory. After that you can start referring to " Introduction to Automata Theory, Languages, and Computation" by Ullman, Hopcraft and Motwani. This is also the reference book for the Automata course (and taught by Ullman) currently being available in Coursera.
on “What is the enlightenment I'm supposed to attain after studying finite automata?” ↗…it's often hard to get hardcopied version (e.g. for documentation) and the content will most probably expire in a year or two. The only technical books I buy in paper are those that don't expire, like "Introduction to Automata Theory, Languages, and Computation" (Hopcroft, Ullman). On the other hand, I read novels almost exclusively on paper. It all boils down to this: I only have so much spare place to keep paper, so I keep in paper only those that I will…
on “Ask HN: Do you still purchase physical books?” ↗…stored. There is also another related proof that says problems are uncountable and programs are countable which means there exist some problems which cannot be solved at all. I would recommend the book Introduction to Automata Theory, Languages, and Computation by Ullman et al. It explains from very simple machine called finite automata to Turing machine. For a beginners introduction Wikipedia entry is still good
on “Show HN: Turing machine simulator in C” ↗