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.
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. 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.
-
CURRENT REVISIONS REFLECT THE LATEST INDUSTRY DEVELOPMENTS WITH NEW EXAMPLES AND EXERCISES TO ENSURE YOUR COMPREHENSION. The latest revisions throughout this edition ensure you are studying the most current theory and practice with additional examples and updated end-of-chapter exercises.
-
ADDITIONAL EXERCISES, PROBLEMS AND EXAMPLES EMPHASIZE THE PRACTICAL APPLICATION OF THEORY YOU ARE LEARNING. New exercises as well as additional memorable examples in specific key areas of theory help you master definitions as well as expand on the most pertinent concepts to further your understanding and ensure success in applying what you've learned.
-
EXPANDED MATH COVERAGE REVIEWS THE FUNDAMENTALS FOR THOSE WHO NEED SUPPORT. This edition offers slightly expanded coverage of important mathematical concepts in Chapter 0. This is ideal support conveniently at your fingertips if you are struggling with any of the mathematical fundamentals necessary for further study in 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.
-
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.
-
FORMAL AND INFORMAL DEFINITIONS AND DESCRIPTIONS INCREASE STUDENT RETENTION
-
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.
-
CLEAR COVERAGE THOROUGHLY INTRODUCES THEORETICAL COMPUTING. This edition covers the foundations of theoretical computing designed around theorems and proofs. You learn the fundamental mathematical properties of computer hardware, software and applications as the book blends practical and theoretical aspects in an approachable and concise presentation.
-
FORMAL AND INFORMAL DEFINITIONS AND DESCRIPTIONS INCREASE RETENTION. This edition's exceptional treatment of challenging topics incorporates both formal and informal definitions and descriptions of methods to ensure retention and effectively prepare you for more advanced study.
-
WORKED-OUT EXAMPLES ENCOURAGE UNDERSTANDING. In addition to a wealth of practical, class-tested exercises, this edition offers helpful worked-out examples throughout the text to guide your practice and ensure topics are conducive to learning.
-
READER-FRIENDLY APPROACH MAKES EVEN THE MOST COMPLEX TOPICS APPROACHABLE NO MATTER WHAT YOUR LEVEL OF UNDERSTANDING. Well known for its crystal-clear presentation, this book continues to offer a concise, accessible presentation to computer theory that makes even highly theoretical and often complex topics understandable for students at every level.