Fundamentals of the Theory of Computation: Table of Contents

Preface

  1. Introduction
    1. Some Computing Puzzles
    2. What is Computability
    3. Related Works
    4. Overview of This Book
    5. Exercises
  2. Languages and Problems
    1. Introduction
    2. Symbols, Alphabets, and Strings
    3. Languages
    4. Operations on Languages
    5. Alphabet Encodings
    6. Some Test Languages
    7. How Many Languages Are There?
    8. Problem Representations
    9. Types of Problems
    10. Casting Problems into Languages
    11. Language Operations and Enumeration
    12. Exercises
  3. Regular Expressions and Languages
    1. Introduction
    2. Regular Languages and Constructions
    3. Regular Expressions
    4. Not All Languages Are Regular
    5. Applications of Regular Expressions
    6. Exercises
  4. Machines I - Finite Automata
    1. Introduction
    2. Basic Machine Notions
    3. Deterministic Finite Automata
    4. Nondeterministic Finite Automata
    5. Equivalence of DFAs and C-Programs
    6. Exercises
  5. Properties of Finite-State Languages
    1. Introduction
    2. Machines for Five Language Operations
    3. Regular Expression and DFA Equivalence
    4. Pumping Lemma for Regular Languages
    5. Applications of the Pumping Lemma
    6. Closure Properties and non-Regular Languages
    7. Exercises
  6. Machines II - Stacks and Tapes
    1. Pushdown Automata
    2. Turing Machines
    3. Undecidable Languages
    4. Relations Among Language Classes
  7. Grammars
    1. Introductions
    2. Context-Free Grammars
    3. Closure Properties of Context-Free Languages
    4. Parsing with PDAs
    5. Parsing with DPDAs
    6. Parse Trees and Attribution
    7. Languages That Are Not Context-Free
    8. Exercises
  8. Computational Complexity
    1. Introduction
    2. Asymptotic Notation
    3. Time and Space Complexity
    4. Simulations
    5. Reducibilities
    6. Exercises
    7. Regular Grammars
  9. Circuit Complexity
    1. Introduction
    2. The Boolean Circuit Model of Computation
    3. Circuit Resources
    4. Examples of Boolean Circuits
    5. The Complexity Class NC
    6. Exercises
  10. Feasible Problems
    1. Introduction
    2. Polynomial Time
    3. P-completeness Theory
    4. Examples of P-complete Problems
    5. P-complete Problems and Reductions
    6. Exercises
  11. Intractable Problems
    1. Introduction
    2. Nondeterministic Polynomial Time
    3. NP-completeness Theory
    4. Examples of NP-complete Problems
    5. NP-complete Problems and Reductions
    6. Exercises

 
Computability book | Ray's main page