内容

目次

Introduction Part I: Foundations Chapter 1: MathematicalPreliminaries 1.1 Set Theory 1.2 Cartesian Product, Relations, and Functions1.3 Equivalence Relations 1.4 Countable and Uncountable Sets 1.5Diagonalization and Self-Reference 1.6 Recursive Definitions 1.7 MathematicalInduction 1.8 Directed Graphs Exercises Bibliographic Notes Chapter 2:Languages 2.1 Strings and Languages 2.2 Finite Specification of Languages 2.3Regular Sets and Expressions 2.4 Regular Expressions and Text SearchingExercises Bibliographic Notes Part II: Grammars, Automata, and LanguagesChapter 3: Context-Free Grammars 3.1 Context-Free Grammars and Languages 3.2Examples of Grammars and Languages 3.3 Regular Grammars 3.4 VerifyingGrammars 3.5 Leftmost Derivations and Ambiguity 3.6 Context-Free Grammars andProgramming Language Definition Exercises Bibliographic Notes Chapter 4:Normal Forms for Context-Free Grammars 4.1 Grammar Transformations 4.2Elimination of Rules 4.3 Elimination of Chain Rules 4.4 Useless Symbols 4.5Chomsky Normal Form 4.6 The CYK Algorithm 4.7 Removal of Direct LeftRecursion 4.8 Greibach Normal Form Exercises Bibliographic Notes Chapter 5:Finite Automata 5.1 A Finite-State Machine 5.2 Deterministic Finite Automata5.3 State Diagrams and Examples 5.4 Nondeterministic Finite Automata 5.5Transitions 5.6 Removing Nondeterminism 5.7 DFA Minimization ExercisesBibliographic Notes Chapter 6: Properties of Regular Languages 6.1Finite-State Acceptance of Regular Languages 6.2 Expression Graphs 6.3Regular Grammars and Finite Automata 6.4 Closure Properties of RegularLanguages 6.5 A Nonregular Language 6.6 The Pumping Lemma for RegularLanguages 6.7 The Myhill-Nerode Theorem Exercises Bibliographic NotesChapter 7: Pushdown Automata and Context-Free Languages 7.1 Pushdown Automata7.2 Variations on the PDA Theme 7.3 Acceptance of Context-Free Languages 7.4The Pumping Lemma for Context-Free Languages 7.5 Closure Properties ofContext-Free Languages Exercises Bibliographic Notes Part III: ComputabilityChapter 8: Turing Machines 8.1 The Standard Turing Machine 8.2 TuringMachines as Language Acceptors 8.3 Alternative Acceptance Criteria 8.4Multitrack Machines 8.5 Two-Way Tape Machines 8.6 Multitape Machines 8.7Nondeterministic Turing Machines 8.8 Turing Machines as Language EnumeratorsExercises Bibliographic Notes Chapter 9: Turing Computable Functions 9.1Computation of Functions 9.2 Numeric Computation 9.3 Sequential Operation ofTuring Machines 9.4 Composition of Functions 9.5 Uncomputable Functions 9.6Toward a Programming Language Exercises Bibliographic Notes Chapter 10: TheChomsky Hierarchy 10.1 Unrestricted Grammars 10.2 Context-Sensitive Grammars10.3 Linear-Bounded Automata 10.4 The Chomsky Hierarchy ExercisesBibliographic Notes Chapter 11: Decision Problems and the Church-TuringThesis 11.1 Representation of Decision Problems 11.2 Decision Problems andRecursive Languages 11.3 Problem Reduction 11.4 The Church-Turing Thesis 11.5A Universal Turing Machine Exercises Bibliographic Notes Chapter 12:Undecidability 12.1 The Halting Problem for Turing Machines 12.2 ProblemReduction and Undecidability 12.3 Additional Halting Problem Reductions 12.4Rice's Theorem 12.5 An Unsolvable Word Problem 12.6 The Post CorrespondenceProblem 12.7 Undecidable Problems in Context-Free Grammars ExercisesBibliographic Notes Chapter 13: Mu-Recursive Functions 13.1 PrimitiveRecursive Functions 13.2 Some Primitive Recursive Functions 13.3 BoundedOperators 13.4 Division Functions 13.5 G odel Numbering and Course-of-ValuesRecursion 13.6 Computable Partial Functions 13.7 Turing Computability andMu-Recursive Functions 13.8 The Church-Turing Thesis Revisited ExercisesBibliographic Notes Part IV: Computational Complexity Chapter 14: TimeComplexity 14.1 Measurement of Complexity 14.2 Rates of Growth 14.3 TimeComplexity of a Turing Machine 14.4 Complexity and Turing Machine Variations14.5 Linear Speedup 14.6 Properties of Time Complexity of Languages 14.7Simulation of Computer Computations Exercises Bibliographic Notes Chapter15: P, NP, and Cook's Theorem 15.1 Time Complexity of Nondeterministic TuringMachines 15.2 The Classes P and NP 15.3 Problem Representation and Complexity15.4 Decision Problems and Complexity Classes 15.5 The Hamiltonian CircuitProblem 15.6 Polynomial-Time Reduction 15.7 P = NP? 15.8 The SatisfiabilityProblem 15.9 Complexity Class Relations Exercises Bibliographic NotesChapter 16: NP-Complete Problems 16.1 Reduction and NP-Complete Problems 16.2The 3-Satisfiability Problem 16.3 Reductions from 3-Satisfiability 16.4Reduction and Subproblems 16.5 Optimization Problems 16.6 ApproximationAlgorithms 16.7 Approximation Schemes Exercises Bibliographic Notes Chapter17: Additional Complexity Classes 17.1 Derivative Complexity Classes 17.2Space Complexity 17.3 Relations between Space and Time Complexity 17.3P-Space, NP-Space, and Savitch's Theorem 17.4 P-Space Completeness 17.5 AnIntractable Problem Exercises Bibliographic Notes Part V: DeterministicParsing Chapter 18: Parsing: An Introduction 18.1 The Graph of a Grammar18.2 A Top-Down Parser 18.3 Reductions and Bottom-Up Parsing 18.4 A Bottom-UpParser 18.5 Parsing and Compiling Exercises Bibliographic Notes Chapter 19:LL(k) Grammars 19.1 Lookahead in Context-Free Grammars 19.2 FIRST, FOLLOW,and Lookahead Sets 19.3 Strong LL(k) Grammars 19.4 Construction of FIRSTkSets 19.5 Construction of FOLLOWk Sets 19.6 A Strong LL(l) Grammar 19.7 AStrong LL(k) Parser 19.8 LL(k) Grammars Exercises Bibliographic NotesChapter 20: LR(k) Grammars 20.1 LR(0) Contexts 20.2 An LR(0) Parser 20.3 TheLR(0) Machine 20.4 Acceptance by the LR(0) Machine 20.5 LR(1) GrammarsExercises Bibliographic Notes Appendix I Index of Notation Appendix II TheGreek Alphabet Appendix III Table of ASCII Characters Appendix IVBackus-Naur Definition of Java Bibliography Subject Index