To the To the educatorvThe frst editionviFeedback to the iPreface to the Second Preface to the Third 0 Introduction.10.1 Automata, Computability, and Complexity.1Complexity theory.2Computability theory.3Automata theory30.2 Mathematical Notions and Terminology3Sets.3Sequences and tuples.6Functions and relations7Graphs.10Strings and languages.13Boolean logic14Summary of mathematical terms.160.3 Defnitions, Theorems, and Proofs.17Finding proofs.170.4 Typesof Proof21Proof by construction.21Proof by contradiction.21Proof by induction.22Exercises, Problems, and Solutions.25PartOne: AutomataandLanguages.291 RegularLanguages.311.1 Finite Automata.31Formal defnition of afnite automaton.35Examples of fnite automata37Formal defnition of computation40Designing fnite automata.41The regular operations441.2 Nondeterminism.47Formal defnition of a nondeterministic fnite automaton53Equivalence of NFAs and DFAs.54Closure under the regular operations.581.3 Regular Expressions.63Formal defnition of a regular expression64Equivalence with fnite automata.661.4 Nonregular Languages77The pumping lemma for regular languages.77Exercises, Problems, and Solutions.832 Context-Free Languages.1012.1 Context-Free Grammars.102Formal defnition of acontext-free grammar104Examples of context-free grammars.105Designing context-free grammars106Ambiguity.107Chomsky normal form1082.2 Pushdown Automata.111Formal defnition of a pushdown automaton.113Example of pushdow automata.114Equivalence with context-free grammars.1172.3Non-Context-Free Languages125The pumping lemma for context-free languages.1252.4 Deterministic Context-Free Languages.130Properties of DCFLs.133Deterministic context-free grammars135Relationship of DPDAs and DCFGs.146Parsing and LR(k) grammars.151Exercises, Problems, and Solutions.154PartTwo: Computability Theory.1633 The Church–Turing Thesis.1653.1 Turing Machines.165Formal defnition of a Turing machine167Examples of Turing machines.1703.2 Variants of Turing Machines.176Multitape Turing machines176Nondeterministic Turing machines178Enumerators180Equivalence with other models1813.3 The Defnition of Algorithm182Hilbert’s problems.182Terminology for describing Turing machines184Exercises, Problems, and Solutions.1874 Decidability.1934.1 Decidable Languages.194Decidable problems concerning regular languages.194Decidable problems concerning context-free languages.1984.2 Undecidability201The diagonalization method.202An undecidable language.207A Turing-unrecognizable language209Exercises, Problems, and Solutions.2105 Reducibility.2155.1 Undecidable Problems from Language Theory216Reductions via computation histories.2205.2 A Simple Undecidable Problem.2275.3 Mapping Reducibility234Computable functions.234Formal defnition of mapping reducibility235Exercises, Problems, and Solutions.2396 Advanced Topicsin Computability Theory.2456.1 The Recursion Theorem.245Self-reference.246Terminology for the recursion theorem.249Applications2506.2 Decidability of logical theories.252A decidable theory.255An undecidable theory.2576.3 Turing Reducibility2606.4 A Defnition of Information.261Minimal length descriptions.262Optimality of the defnition266Incompressible strings and randomness.267Exercises, Problems, and Solutions.270Part Three: Complexity Theory.2737 Time Complexity.2757.1 Measuring Complexity275Big-O and small-o notation276Analyzing algorithms.279Complexity relationships among models.2827.2 The Class P284Polynomial time284Examples of problems in P2867.3 The Class NP.292Examples of problemsin NP.295The Pversus NP question2977.4 NP-completeness.299Polynomial time reducibility.300Defnition of NP-completeness304The Cook–Levin Theorem3047.5 Additional NP-complete Problems.311The vertex cover problem.312The Hamilto