Higher Education

product-details

Introduction to the Theory of Computation

Author(s): Michael Sipser

ISBN: 9788131525296

3rd Edition

Copyright: 2013

India Release: 2014

₹660

Binding: Paperback

Pages: 480

Trim Size: 241 x 181 mm

Refer Book

Order Inspection Copy

"Introduction to the Theory of Computation, 3E" by Sipser is the go-to text for computational theory courses. The revised edition maintains its clear and thorough coverage, with added exercises and memorable examples. Noteworthy updates include a theoretical treatment of deterministic context-free languages. The book strikes a balance between accessibility, rigor, and formalism, providing a solid understanding of mathematical properties in computer hardware, software, and applications. It serves as an ongoing reference tool for theoretical computing studies.

 

  • Clear coverage introduces theoretical computing with a focus on theorems and proofs.
  • Formal and informal definitions enhance student retention and understanding.
  • Worked-out examples guide student practice and comprehension.
  • Reader-friendly approach makes complex topics approachable at all levels.
  • Current revisions reflect industry developments with new examples and exercises.
  • Additional exercises and examples emphasize practical application of theory.
  • Expanded math topics provide support for students who need review.
  • New coverage of deterministic context-free languages explains complex topics clearly and thoroughly.

Introduction.

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.

Michael Sipser

Michael Sipser has taught theoretical computer science and mathematics at the Massachusetts Institute of Technology for the past 32 years