Request for consultation

Thanks for your request. You’ll soon be chatting with a consultant to get the answers you need.
{{formPostErrorMessage.message}} [{{formPostErrorMessage.code}}]
First Name is required. 'First Name' must contain at least 0 characters 'First Name' cannot exceed 0 characters Please enter a valid First Name
Last Name is required. 'Last Name' must contain at least 0 characters 'Last Name' cannot exceed 0 characters Please enter a valid Last Name
Institution is required.
Discipline is required.
Why are you contacting us today? is required. 'Why are you contacting us today?' must contain at least 0 characters 'Why are you contacting us today?' cannot exceed 0 characters Please enter a valid Why are you contacting us today?

Introduction to the Theory of Computation 3rd Edition

Michael Sipser

  • Published
  • Previous Editions 2006, 1997, 1996
  • 504 Pages


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(k) 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's comprehensive coverage makes this an ideal ongoing reference tool for those studying theoretical computing.

Michael Sipser, Massachusetts Institute of Technology

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.
  • CURRENT REVISIONS REFLECT THE LATEST INDUSTRY DEVELOPMENTS WITH NEW EXAMPLES AND EXERCISES TO ENSURE COMPREHENSION. The latest revisions throughout this edition ensure readers are studying the most current theory and practice with additional examples and updated end-of-chapter exercises. Refined presentations throughout ensure the latest accuracy and relevency.
  • ADDITIONAL EXERCISES, PROBLEMS AND EXAMPLES EMPHASIZE THE PRACTICAL APPLICATION OF THEORY. New classroom-tested exercises with corresponding solutions as well as additional memorable examples in specific key areas review definitions and expand on concepts to challenge and extend your students' understanding.
  • EXPANDED MATH TOPICS OFFERS SUPPORT FOR READERS WHO NEED REVIEW. This edition offers slightly expanded coverage of important mathematical concepts in Chapter 0, which is ideal for any students struggling with the mathematical fundamentals necessary for this course.
  • NEW COVERAGE OF DETERMINISTRIC CONTEXT-FREE LANGUAGES PROVIDES UNIQUE, CLEAR AND THOROUGH EXPLANATION. A new section in Chapter 2 (Context-Free Languages) covers deterministic context-free languages with application to the parsing problem in compilers and programming languages. This first-of-its-kind, understandable theoretical treatment explains this highly complex, but critical, topic and its applications thoroughly and clearly. Coverage includes deterministic pushdown automata, deterministic context-free grammars, and more.
  • CLEAR COVERAGE THOROUGHLY INTRODUCES THEORETICAL COMPUTING. This edition covers the foundations of theoretical computing designed around theorems and proofs. Students learn the fundamental mathematical properties of computer hardware, software and applications. The book blends both practical and theoretical aspects in an approachable and concise presentation.
  • This edition's exceptional treatment of challenging topics incorporates both formal and informal definitions and descriptions of methods to ensure student retention and prepare readers for more advanced study.
  • WORKED-OUT EXAMPLES ENCOURAGE READER UNDERSTANDING. In addition to a wealth of practical, class-tested exercises, this edition offers helpful worked-out examples throughout the text to guide student practice and ensure topics are conducive to students' learning.
  • READER-FRIENDLY APPROACH MAKES EVEN THE MOST COMPLEX TOPICS APPROACHABLE FOR STUDENTS AT ALL LEVELS. Well known for its crystal-clear presentation, this book continues to offer a concise, accessible presentation to computer theory that makes even complex topics understandable for students at every level.
1. Regular Languages.
2. Context-Free Languages.
3. The Church-Turing Thesis.
4. Decidability.
5. Reducibility.
6. Advanced Topics in Computability Theory.
7. Time Complexity.
8. Space Complexity.
9. Intractability.
10. Advanced Topics in Complexity Theory.
Selected Bibliography.

Textbook Only Options

Traditional eBook and Print Options

{{collapseContainerClosed['detail_0'] ? 'Show More' : 'Show Less'}}

  • ISBN-10: 1285320735
  • ISBN-13: 9781285320731
  • STARTING AT $21.99

  • STARTING AT $43.49

  • ISBN-10: 113318779X
  • ISBN-13: 9781133187790
  • Bookstore Wholesale Price $204.00
  • RETAIL $271.95

"The text meets my objectives very well. The author presents the material in an appealing manner, making a hard subject accessible and intuitive to the students. He manages to do that while maintaining the rigor and formalism that the subject warrants. The book has a lot of information packed in it, and can serve as a reference book for students interested in research in theoretical CS."

"As one of my students puts it, the book is 'fun to read and helps him learn the subject better'."

"This is a model for readability, with sensitivity for what students find difficult."

"Excellent prose (simple and succinct) with very good diagrams. It is by far the best presentation of automata in the business."

Cengage provides a range of supplements that are updated in coordination with the main title selection. For more information about these supplements, contact your Learning Consultant.


Solutions Manual

ISBN: 9781133188650
Written by the text book author to ensure accuracy and continuity with the text, this straight-forward Solutions Manual offers trusted solutions that correspond with all of the exercises in this edition. Please note: this supplement is PRINT ONLY, and not available online. Also, this Solutions Manual and the Instructor Manual are one and the same.