An Introduction to Theory of Computation: An Algorithmic Approach

Description

This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in computer science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation. The book begins with regular languages, exploring finite automata, nondeterministic finite automata, regular expressions, and the equivalence among these apparatuses. It explores state minimization and the Myhill-Nerode Theorem, offering techniques such as pumping lemmas to identify non-regular languages and using the Myhill-Nerode Theorem for non-regularity proofs. Additionally, the closure properties of regular languages are examined. Context-free languages are another focal point, where the text discusses context-free grammars, Chomsky normal form grammars, pushdown automata, and their equivalences. The book includes pumping lemmas and closure properties using CNF grammars and PDA analysis, as well as identifying non-context-free languages and understanding leftmost derivations. Turing machine models are thoroughly covered, with various models and simulations explained. The book outlines configurations, the Church-Turing Thesis, and differentiates between recursive and recursively enumerable languages. Decidability and undecidability are critical topics in the text, addressing decidable problems, diagonalization, the halting problem, and Rice’s Theorem. It also provides a characterization of decidability, discusses the Post Correspondence Problem, and examines the lower levels of the arithmetical hierarchy. The textbook also delves into computational complexity classes, defining time and space complexity classes, and presenting efficient simulations and hierarchy theorems, including the Hennie-Stearns Theorem. It includes examples of problems in P and NP, providing a clear understanding of these classifications. NP-completeness is explored in detail, covering SAT and 3SAT, canonical complete problems, and various NP-complete problems. The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL. Finally, the text ventures beyond NP-completeness, discussing Ladner’s construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy. It also examines polynomial size circuits, providing a comprehensive view of the landscape of computational complexity. Preface Contents List of Figures List of Algorithms Symbols, Acronyms, and Class Names Part I Preparation 1 Mathematics and Computer Science Basics 1.1 Sets 1.1.1 Set Operations 1.2 Boolean Algebra 1.2.1 Implication and Equivalence 1.2.2 Predicates 1.2.3 Truth Assignments and Quantifications 1.3 Functions 1.3.1 Big-O Notation 1.4 Languages 1.4.1 Alphabets and Strings 1.4.2 Languages and Their Classes 1.5 Graphs and Trees 1.5.1 Directed Graphs 1.5.2 Reachability 1.5.3 Undirected Graphs 1.5.4 Trees 1.6 Proof Methods 1.7 Algorithmic Concepts Part II Formal Language Theory and Automata 2 The Regular Languages 2.1 The Finite Automaton (DFA) Model 2.1.1 The Definition 2.1.2 Example DFAs 2.2 The Nondeterministic Finite Automaton (NFA) Model 2.2.1 The Definition 2.2.2 Converting NFAs to DFAs 2.2.2.1 The Pseudo-Nondeterministic Finite Automaton (Pseudo-NFA) Model 2.2.2.2 Converting NFAs to DFAs 2.2.2.3 A Greedy Conversion Algorithm 2.2.3 Constructing Regular Languages from Other Regular Languages 2.3 Regular Expressions 2.3.1 The Definition 2.3.2 Equivalence Between Regular Expressions and NFAs 2.3.3 Visualizing the Construction References 3 Non-regularity 3.1 Minimizing the State Number 3.1.1 A Motivation 3.1.2 Distinguishable State-Pairs 3.2 The Myhill-Nerode Theorem 3.3 Proving Non-regularity 3.3.1 Proving Non-regularity Using the Myhill-Nerode Theorem 3.3.2 Proving Non-regularity Using the Pumping Lemma for Regular Languages 3.3.2.1 The Pumping Lemma 3.3.2.2 Proving Non-regularity Using the Pumping Lemma 3.3.3 Proving Non-regularity Using Closure Properties References 4 The Context-Free Languages 4.1 The Context-Free Grammar (CFG) 4.1.1 The Definition 4.1.2 Examples of CFGs 4.1.3 Production Trees 4.1.4 Leftmost and Rightmost Productions 4.1.5 Closure Properties of CFLs 4.2 Normal Forms of CFGs 4.2.1 The Chomsky Normal Form (CNF) Grammars 4.2.2 Normalizing CFGs to CNF Grammars 4.2.3 The Greibach Normal Form (GNF) Grammars References 5 The Pushdown Automaton Model 5.1 The Pushdown Automaton (PDA) Model 5.1.1 The Definition 5.1.2 Examples of PDAs 5.2 Equivalence Between CFLs and PDAs 5.3 The Deterministic Pushdown Automaton (DPDA) Model 5.4 Proving Non-context-Freeness 5.4.1 The Pumping Lemma for CFLs 5.4.2 Inherent Ambiguity of CFLs 5.4.3 Non-context-Free Languages 5.4.4 Ogden's Lemma 5.4.5 Proving Ogden's Lemma by Analyzing a PDA'sBehavior 5.4.5.1 (Case 1) "026B30D Hk "026B30D ≥4"026B30D Q "026B30D + 1 5.4.5.2 (Case 2) "026B30D Hk "026B30D ≤4 "026B30D Q"026B30D 5.4.5.3 (Subcase 2a) k = , We Have Kept Choosing the Last Block Index p as the Right End of the Interval At Each Step (i.e., r0 = @汥瑀瑯步渠= r = p), and h ≤botp 5.4.5.4 (Subcase 2b) k = = + 5.4.5.5 (Subcase 2c) Neither Subcase 2a Nor Subcase 2b Holds References Part III Undecidability and Turing Machines 6 The Turing Machines 6.1 The Turing Machine (TM) Model 6.1.1 The Definition 6.1.1.1 The Mathematical Definition 6.1.1.2 Recognition and Decision 6.1.2 Examples of TMs 6.1.3 Instantaneous Descriptions 6.1.4 Fundamental Subroutines 6.1.4.1 Restoring the Input 6.1.4.2 Insertion 6.1.4.3 Deletion 6.2 The Multi-tape TM Model 6.2.1 The Definition 6.2.2 Examples of Multi-tape TMs 6.2.3 Simulating Multi-tape TMs Using Single-Tape TMs 6.2.3.1 Discovering the Symbols 6.2.3.2 Determining What to Update 6.2.3.3 Executing the Updates 6.2.3.4 R Is the Intersection of RE and coRE 6.3 The Nondeterministic Turing Machine (NTM) Model 6.4 Alternate Definitions of RE 6.4.1 Enumerators 6.4.2 Witness Schemes 6.5 Computing Functions Using TMs and the Church-TuringThesis References 7 Decidable Languages 7.1 The Universal TM Model 7.1.1 Encoding Schemes 7.1.2 Fundamental Problems 7.1.3 Using Universal TMs 7.2 Decidable Fundamental Problems 7.2.1 Decidable Problems About Regular Languages 7.2.1.1 Acceptance 7.2.1.2 Emptiness 7.2.1.3 Infiniteness 7.2.1.4 Totality 7.2.1.5 Containment 7.2.1.6 Equality 7.2.1.7 Decidable Problems About NFAs and Regular Expressions 7.2.2 Decidable Problems About CFLs References 8 Undecidable Languages 8.1 The Halting Problem 8.1.1 Proving Impossibility Using Diagonalization 8.1.2 The Halting Problem 8.1.3 Some Variants of the Halting Problem 8.2 Many-One Reductions and Rice's Theorem 8.2.1 Many-One Reductions 8.2.2 Rice's Theorem 8.3 Undecidable Problems About CFLs 8.3.1 The Totality Problem About CFLs 8.3.2 Undecidable Problems About DCFLs 8.4 Post's Correspondence Problem (PCP) 8.4.1 The Definitions of PCP and MPCP 8.4.2 The Undecidability of MPCP 8.4.2.1 An Accepting ID Sequence 8.4.2.2 Designing Domino Tiles 8.4.2.3 The Correctness 8.4.3 The Undecidability of PCP 8.5 Beyond RE References Part IV Computational Complexity and Resource-Bounded Turing Machine Computation 9 The Time Complexity 9.1 The Time Complexity Measure 9.2 Time-Efficient Simulations of Multi-tape TMs 9.2.1 Simulating with One Tape 9.2.2 Simulating with Two Tapes 9.2.2.1 The Tape Organization 9.2.2.2 The Tape Coloring and Marking 9.2.2.3 The Simulation Procedure 9.2.2.4 Pushing Blocks to the Right 9.2.2.5 Pulling Blocks from the Right 9.2.2.6 An Analysis of the Running Time 9.3 The Time Hierarchy Theorems 9.4 The Nondeterministic Time Complexity 9.5 Fundamental Time Complexity Classes 9.6 Examples of Time Complexity Classifications 9.6.1 The DFA State Minimization Problem 9.6.2 The Problem of Converting an NFA to a Regular Expression 9.6.3 The CFL Membership Problem References 10 The Space Complexity 10.1 The Space Complexity Measure 10.2 Savitch's Theorem 10.3 Fundamental Space Complexity Classes 10.4 The Reachability Problem 10.5 Examples of Space Complexity Classifications References 11 The Theory of NP-Completeness 11.1 The Polynomial-Time Many-One Reducibility 11.1.1 The Definition 11.1.1.1 Examples of Polynomial-Time Many-One Reductions 11.1.2 The Definition of NP-Complete Languages 11.1.3 A Canonical NP-Complete Language 11.1.4 Polynomial-Time Witness Schemes 11.2 The Satisfiability Problem (SAT) 11.2.1 The NP-Completeness of SAT 11.2.2 NP-Complete Variants of SAT 11.2.2.1 The CNF Satisfiability 11.2.2.2 3SAT 11.2.2.3 NAE-SAT 11.2.3 Some Complete Problems for coNP 11.3 Fundamental NP-Complete Problems 11.3.1 The Clique Problem 11.3.2 The Vertex Cover Problem 11.3.3 The 3-Coloring Problem 11.3.4 The Hamilton Path Problem 11.3.5 NP-Completes Problems About Integers 11.3.5.1 The Partition Problem 11.3.5.2 The Knapsack Problem 11.3.5.3 The Scheduling Problem 11.3.6 NP-Complete Problems About Matching and Set Partitioning 11.3.7 More Examples of NP-Complete Problems 11.3.7.1 Exact Cover by Three Sets (X3C) 11.3.7.2 The Independent Set Problem References 12 Beyond NP-Completeness 12.1 The Complexity of Finding a Witness 12.2 The Polynomial-Time Turing Reducibility 12.2.1 The Problem of Finding the Least SatisfyingAssignment 12.3 The Polynomial Hierarchy (PH) 12.3.1 The Definition 12.3.2 Logical Characterizations of PH 12.4 Between P and NP-Complete 12.4.1 Two Enumerations of TMs 12.4.2 T's Program 12.4.3 T's Running Time 12.4.4 t's Range and Its Non-decreasing Property 12.4.5 t's Unboundedness 12.4.6 The Final Touch 12.5 PSPACE-Complete Problems 12.5.1 Quantified Boolean Formulas (QBF) 12.5.2 Games and Winning Strategies 12.5.3 The Geography Game References Part V Advanced Topics in Computational Complexity Theory 13 The Probabilistic Polynomial-Time Classes 13.1 The Probabilistic Turing Machine Model 13.1.1 The Definition 13.2 Primality Testing Algorithms 13.2.1 Number Theory Basics 13.2.1.1 Fermat's Little Theorem 13.2.1.2 The Chinese Remainder Theorem 13.2.1.3 Generators 13.2.2 The Miller-Rabin Test 13.2.2.1 Miller's Algorithm 13.2.3 The Polynomial Zero-Testing Problem 13.3 Relations Between BPP and PH 13.4 The Class PP References 14 Circuit Complexity and Unambiguity 14.1 The Circuit Computation Models 14.1.1 The Boolean Circuit Model 14.1.2 Relations Between Boolean Circuit-Based Classes and TM-Based Classes 14.1.3 The Arithmetic Circuit Model 14.2 The Class P/poly 14.3 Unambiguous Accepting Computation Paths of NTMs References A A List of Major Results A.1 Characterizations of Language Classes A.2 Relations Between Language Classes A.3 Closure Properties of Language Classes A.4 Non-closure Properties of Language Classes A.5 Classifications of Specific Languages A.6 Polynomial-Time Many-One and Witness Reductions A.7 Pumping Lemmas A.8 Normalization and Behavior of Computing Objects A.9 Time and Space Constructibility A.10 Number and Probability Theories Index