Introduction to the Theory of Computation, 3rd Edition

Gain a clear understanding of even the most complex, highly theoretical computational theory topics in the approachable presentation found only in the market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today’s computational theory course, this revision continues the book’s well-know, approachable style with timely revisions, additional practice, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. You gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E’s comprehensive coverage makes this a valuable reference for your continued studies in theoretical computing.

Table of Contents

Part 1: Automata and Languages
Chapter 1: Regular Languages
Chapter 2: Context-Free Languages
Part 2: Computability Theory
Chapter 3: The Church–Turing Thesis
Chapter 4: Decidability
Chapter 5: Reducibility
Chapter 6: Advanced Topics in Computability Theory
Part 3: Complexity Theory
Chapter 7: Time Complexity
Chapter 8: Space Complexity
Chapter 9: Intractability
Chapter 10: Advanced Topics in Complexity Theory