Introduction to the Theory of Computation
Kaup valmöguleikar
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.
Nánar um bókina
- Cengage Learning US
- 9781285401065
- 9780357670583
- Page Fidelity (PDF)
- 3
- Michael Sipser
- English
- 2021-01-29
- 100
- 2
- 2
Kaflar
- Title
- Statement
- Copyright
- Dedication
- Contents
- Preface to the First Edition
- Preface to the Second Edition
- Preface to the Third Edition
- Ch 0: Introduction
- 0.1 Automata, Computability, and Complexity
- 0.2 Mathematical Notions and Terminology
- 0.3 Definitions, Theorems, and Proofs
- 0.4 Types of Proof
- Exercises
- Problems
- Selected Solutions
- Part 1: Automata and Languages
- Ch 1: Regular Languages
- Introduction
- 1.1 Finite Automata
- 1.2 Nondeterminism
- 1.3 Regular Expressions
- 1.4 Nonregular Languages
- Exercises
- Problems
- Selected Solutions
- Ch 2: Context-Free Languages
- Introduction
- 2.1 Context-Free Grammars
- 2.2 Pushdown Automata
- 2.3 Non-Context-Free Languages
- 2.4 Deterministic Context-Free Languages
- Exercises
- Problems
- Selected Solutions
- Part 2: Computability Theory
- Ch 3: The Church–Turing Thesis
- Introduction
- 3.1 Turing Machines
- 3.2 Variants of Turing Machines
- 3.3 The Definition of Algorithm
- Exercises
- Problems
- Selected Solutions
- Ch 4: Decidability
- Introduction
- 4.1 Decidable Languages
- 4.2 Undecidability
- Exercises
- Problems
- Selected Solutions
- Ch 5: Reducibility
- Introduction
- 5.1 Undecidable Problems From Language Theory
- 5.2 A Simple Undecidable Problem
- 5.3 Mapping Reducibility
- Exercises
- Problems
- Selected Solutions
- Ch 6: Advanced Topics in Computability Theory
- Introduction
- 6.1 The Recursion Theorem
- 6.2 Decidability of logical theories
- 6.3 Turing Reducibility
- 6.4 A Definition of Information
- Exercises
- Problems
- Selected Solutions
- Part 3: Complexity Theory
- Ch 7: Time Complexity
- Introduction
- 7.1 Measuring Complexity
- 7.2 The Class P
- 7.3 The Class NP
- 7.4 NP-completeness
- 7.5 Additional NP-complete Problems
- Exercises
- Problems
- Selected Solutions
- Ch 8: Space Complexity
- Introduction
- 8.1 Savitch’s Theorem
- 8.2 The Class PSPACE
- 8.3 PSPACE-completeness
- 8.4 The Classes L and NL
- 8.5 NL-completeness
- 8.6 NL equals coNL
- Exercises
- Problems
- Selected Solutions
- Ch 9: Intractability
- Introduction
- 9.1 Hierarchy Theorems
- 9.2 Relativization
- 9.3 Circuit Complexity
- Exercises
- Problems
- Selected Solutions
- Ch 10: Advanced Topics in Complexity Theory
- Introduction
- 10.1 Approximation Algorithms
- 10.2 Probabilistic Algorithms
- 10.3 Alternation
- 10.4 Interactive Proof Systems
- 10.5 Parallel Computation
- 10.6 Cryptography
- Exercises
- Problems
- Selected Solutions
- Selected Bibliography
- Index