Introduction to the Theory of Computation
by Michael Sipser · Michael Sipser
The standard undergraduate text on automata, context-free languages, Turing machines, decidability, and complexity classes including NP-completeness. Its proofs are written out in full, so readers learn to construct formal arguments about what machines can compute.
This link may earn us a small commission at no extra cost to you. Affiliate disclosure
More resources on Theory of Computation
theoryofcomputing.org
Theoryofcomputing.org is a practical resource hub for theory of computation, featuring lecture notes, tutorials, and problem sets on automata, formal languages, computability, and complexity to help learners build intuition and tackle exercises.
NFA to DFA Converter
Browser-based simulator by Kyle Dickerson for building DFAs, NFAs, and pushdown automata, then running inputs through them singly or in bulk. Useful for checking by hand whether a machine you designed accepts the right language.
Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT 6.890)
Techniques for proving problems computationally hard: NP-hardness reductions, gadget design, games and puzzles, PSPACE-completeness, inapproximability and fixed-parameter hardness. Includes 23 lecture videos, lecture notes, and problem sets with solutions. Afterwards you can construct reductions showing a problem likely has no efficient algorithm.
Introduction to Algorithms (MIT 6.006)
Modeling computational problems and solving them with core algorithms and data structures: sorting, hashing, binary trees, heaps, graph search, shortest paths and dynamic programming. 32 lecture videos, notes, problem sets and exams with solutions teach asymptotic analysis and algorithm design.
Theory of Computation
Learn computability theory with Kamala Krithivasan's Theory of Computation course. Explore fundamental concepts and problem-solving!
Theory of Computation (MIT 18.404J)
Sipser's course on automata, computability and complexity: regular and context-free languages, decidability, reducibility, the recursion theorem, time and space complexity, NP-completeness, hierarchy theorems, probabilistic computation and interactive proofs. 25 lecture videos, slides, problem sets and exams support rigorous proof-based study.