Description
Introduction to the Theory of Computation develops the mathematical foundations of computer science through the study of automata, computability, and computational complexity. It introduces regular languages, finite automata, nondeterminism, regular expressions, context-free languages, and Turing machines before examining decidability and reducibility. The book then explores time and space complexity, polynomial-time computation, NP-completeness, and the limits of efficient computation. The Third International Edition also includes deterministic context-free languages and additional exercises and problems. With formal definitions, proofs, examples, and problem-solving exercises, the text provides a rigorous foundation for understanding what computers can compute, how computational problems are classified, and why some problems are inherently difficult.
