Introduction to the Theory of Computation

Author: Michael Sipser

Errata

CONTENTS OF THE PRELIMINARY EDITION

0. Introduction

  1. AUTOMATA, COMPUTABILITY, AND COMPLEXITY
    Complexity theory - Computability theory - Automata theory
  2. MATHEMATICAL NOTIONS AND TERMINOLOGY
    Sets - Sequences and tuples - Functions and relations - Graphs - Strings and languages - Summary of mathematical terms
  3. DEFINITIONS, THEOREMS, AND PROOFS
    Finding proofs
  4. TYPES OF PROOF
    Proof by construction - Proof by contradiction - Proof by induction
  5. EXERCISES AND PROBLEMS

PART I: AUTOMATA AND LANGUAGES

1. Regular Languages

  1. FINITE AUTOMATA
    Formal definition of a finite automaton - Examples of finite automata - Formal definition of computation - Designing finite automata - The regular operations
  2. NONDETERMINISM
    Formal definition of a nondeterministic finite automaton - Equivalence of nfas and dfas
  3. REGULAR EXPRESSIONS
    Formal definition of a regular expression - Equivalence with finite automata
  4. NONREGULAR LANGUAGES
    The pumping lemma for regular languages
  5. EXERCISES AND PROBLEMS

2. Context-free Languages

  1. CONTEXT-FREE GRAMMARS
    Formal definition of a context-free grammar - Examples of context-free grammars - Ambiguity - Chomsky normal form
  2. PUSHDOWN AUTOMATA
    Formal definition of a pushdown automaton - Examples of pushdown automata - Equivalence with context-free grammars
  3. NON-CONTEXT-FREE LANGUAGES
    The pumping lemma for context-free languages
  4. EXERCISES AND PROBLEMS

PART II: COMPUTABILITY THEORY

3. The Church-Turing Thesis

  1. TURING MACHINES
    Formal definition of a Turing machine - Examples of Turing machines
  2. VARIANTS OF TURING MACHINES
    Multitape Turing machines - Nondeterministic Turing machines - Enumerators - Equivalence with other models
  3. THE DEFINITION OF ALGORITHM
    Hilbert's Problems - Terminology for describing Turing machines
  4. EXERCISES AND PROBLEMS

4. Decidability

  1. DECIDABLE LANGUAGES
    Decidable problems concerning regular languages - Decidable problems concerning context-free languages
  2. THE HALTING PROBLEM
    The diagonalization method - The halting problem is undecidable - A nonenumerable language
  3. EXERCISES AND PROBLEMS

5. Reducibility

  1. UNDECIDABLE PROBLEMS FROM LANGUAGE THEORY
    Reductions via computation histories
  2. A SIMPLE UNDECIDABLE PROBLEM
  3. MAPPING REDUCIBILITY
    Computable functions - Formal definition of mapping reducibility
  4. EXERCISES AND PROBLEMS

6. The Recursion Theorem

  1. SELF-REFERENCE
    Terminology for the Recursion Theorem
  2. APPLICATIONS
  3. EXERCISES AND PROBLEMS

PART III: COMPLEXITY THEORY

7. Time Complexity

  1. MEASURING COMPLEXITY
    Big-O and small-o notation - Analyzing algorithms - Complexity relationships among models
  2. THE CLASS P
    Polynomial time - Examples of problems in P
  3. THE CLASS NP
    Examples of problems in NP - The P versus NP question
  4. NP-COMPLETENESS
    Polynomial time reducibility - Definition of NP-completeness - The Cook--Levin Theorem
  5. EXAMPLES OF NP-COMPLETE PROBLEMS
  6. EXERCISES AND PROBLEMS
First Edition