Introduction to the Theory of Computation 3rd Edition


  • Author: Michael Sipser
  • Publisher: Cengage Learning
  • ISBN-13: 9788131525296
  • Pages: 480
  • Binding: Paperback
  • Year of Pub / Reprint Year: 2013

Out of stock


Now you can clearly present even the most complex computational theory topics to your students with Sipser’s distinct, market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today’s computational theory course, this highly anticipated revision retains the unmatched clarity and thorough coverage that make it a leading text for upper-level undergraduate and introductory graduate students. This edition continues author Michael Sipser’s well-known, approachable style with timely revisions, additional exercises, 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 grammars. This edition’s refined presentation ensures a trusted accuracy and clarity that make the challenging study of computational theory accessible and intuitive to students while maintaining the subject’s rigor and formalism. Readers 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, comprehensive coverage makes this an ideal ongoing reference tool for those studying theoretical computing.

About the Author

Michael Sipser Michael Sipser has taught theoretical computer science and mathematics at the Massachusetts Institute of Technology for the past 32 years. He is a Professor of Applied Mathematics, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and the current head of the mathematics department. He enjoys teaching and pondering the many mysteries of complexity theory.

Table of Contents

PART 1: AUTOMATA AND LANGUAGES. 1. Regular Languages.
2. Context-Free Languages.
PART 2: COMPUTABILITY THEORY. 3. The Church-Turing Thesis.
4. Decidability.
5. Reducibility.
6. Advanced Topics in Computability Theory.
PART 3: COMPLEXITY THEORY. 7. Time Complexity.
8. Space Complexity.
9. Intractability.
10. Advanced Topics in Complexity Theory.
Selected Bibliography.