| |
| |
| Introduction | |
| |
| |
| |
| Foundations | |
| |
| |
| |
| Mathematical Preliminaries | |
| |
| |
| Set Theory | |
| |
| |
| Cartesian Product, Relations, and Functions | |
| |
| |
| Equivalence Relations | |
| |
| |
| Countable and Uncountable Sets | |
| |
| |
| Recursive Definitions | |
| |
| |
| Mathematical Induction | |
| |
| |
| Directed Graphs | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Languages | |
| |
| |
| Strings and Languages | |
| |
| |
| Finite Specification of Languages | |
| |
| |
| Regular Sets and Expressions | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Context-Free Grammars And Parsing | |
| |
| |
| |
| Context-Free Grammars | |
| |
| |
| Context-Free Grammars and Languages | |
| |
| |
| Examples of Grammars and Languages | |
| |
| |
| Regular Grammars | |
| |
| |
| Grammars and Languages Revisited | |
| |
| |
| A Context-Free Grammar for Pascal | |
| |
| |
| Arithmetic Expressions | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Parsing: An Introduction | |
| |
| |
| Leftmost Derivations and Ambiguity | |
| |
| |
| The Graph of a Grammar | |
| |
| |
| A Breadth-First Top-Down Parser | |
| |
| |
| A Depth-First Top-Down Parser | |
| |
| |
| Bottom-Up Parsing | |
| |
| |
| A Shift-Reduce Parser | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Normal Forms | |
| |
| |
| Elimination of Lambda Rules | |
| |
| |
| Elimination of Chain Rules | |
| |
| |
| Useless Symbols | |
| |
| |
| Chomsky Normal Form | |
| |
| |
| Removal of Direct Left Recursion | |
| |
| |
| Greibach Normal Form | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Automata And Languages | |
| |
| |
| |
| Finite Automata | |
| |
| |
| A Finite-State Machine | |
| |
| |
| Deterministic Finite Automata | |
| |
| |
| State Diagrams and Examples | |
| |
| |
| Nondeterministic Finite Automata | |
| |
| |
| Lambda Transitions | |
| |
| |
| Removing Nondeterminism | |
| |
| |
| DFA Minimization | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Regular Languages and Sets | |
| |
| |
| Finite Automata and Regular Sets | |
| |
| |
| Expression Graphs | |
| |
| |
| Regular Grammars & Finite Automata | |
| |
| |
| Closure Properties of Regular Languages | |
| |
| |
| A Nonregular Language | |
| |
| |
| The Pumping Lemma for Regular Languages | |
| |
| |
| Myhill-Nerode Theorem | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Pushdown Automata and Context-Free Languages | |
| |
| |
| Variations on the PDA Theme | |
| |
| |
| Pushdown Automaton and Context-Free Languages | |
| |
| |
| The Pumping Lemma for Context-Free Languages | |
| |
| |
| Closure Properties of Context-Free Languages | |
| |
| |
| A Two-Stack Automation | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Turing Machines | |
| |
| |
| The Standard Turing Machine | |
| |
| |
| Turing Machines as Language Acceptors | |
| |
| |
| Alternate Acceptance Criteria | |
| |
| |
| Multitrack Machines | |
| |
| |
| Two-Way Tape | |
| |
| |
| Multitape Machines | |
| |
| |
| Nondeterministic Turing Machines | |
| |
| |
| Turing Machines as Language Enumerators | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| The Chomsky Hierarchy | |
| |
| |
| Unrestricted Grammars | |
| |
| |
| Context-Sensitive Grammars | |
| |
| |
| Linear-Bounded Automata | |
| |
| |
| The Chomsky Hierarchy | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Decidability And Computablity | |
| |
| |
| |
| Decidability | |
| |
| |
| Decision Problems | |
| |
| |
| The Church-Turing Thesis | |
| |
| |
| The Halting Problem for Turing Machines | |
| |
| |
| A Universal Machine | |
| |
| |
| Reducibility | |
| |
| |
| Rice''s Theorem | |
| |
| |
| An Unsolvable Word Problem | |
| |
| |
| The Post Correspondence Problem | |
| |
| |
| Undecidable Problems in Context- Free Grammars | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Numeric Computation | |
| |
| |
| Computation of Functions | |
| |
| |
| Sequential Operation of Turing Machines | |
| |
| |
| Composition of Functions | |
| |
| |
| Toward a Programming Languages | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Mu-Recursive Functions | |
| |
| |
| Primitive Recursive Functions | |
| |
| |
| Some Primitive Recursive Functions | |
| |
| |
| Bounded Operators | |
| |
| |
| Division Functions | |
| |
| |
| G�del Numbering and Course-of-Values Recursion | |
| |
| |
| Computable Partial Functions | |
| |
| |
| Turing Computability and Mu-Recursive Functions | |
| |
| |
| The Church-Turing Thesis Revisited | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| V | |
| |
| |
| |
| Computational Complexity | |
| |
| |
| Time Complexity of a Turing Machine | |
| |
| |
| Linear Speed-Up | |
| |
| |
| Rates of Growth | |
| |
| |
| Complexity and Turing Machine Variations | |
| |
| |
| Variations of Time Complexity | |
| |
| |
| Nondeterministic Complexity | |
| |
| |
| Space Complexity | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Tractability and NP-Complete Problems | |
| |
| |
| Tractable and Intractable Decision Problems | |
| |
| |
| The Class NP | |
| |
| |
| P=NP | |
| |
| |
| The Satisfiability Problem | |
| |
| |
| Additional NP-Complete Problems | |
| |
| |
| Derivative Complexity Classes | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Deterministic Parsing | |
| |
| |
| |
| LL (k) Grammars | |
| |
| |
| Lookahead in Context-Free Grammars | |
| |
| |
| First, Follow, and Lookahead Sets | |
| |
| |
| Strong LL (k) Grammars | |
| |
| |
| Construction of FIRSTk Sets | |
| |
| |
| Construction of FOLLOWk Sets | |
| |
| |
| A Strong LL(1) Grammar | |
| |
| |
| A Strong LL(k) Parser | |
| |
| |
| LL(k) Grammars | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| LR(k) Grammars | |
| |
| |
| LR(0) Contexts | |
| |
| |
| LR(0) Parser | |
| |
| |
| LR(0) Machine | |
| |
| |
| Acceptance by the LR(0) Machine | |
| |
| |
| Acceptance by the LR(p) Machine | |
| |
| |
| LR(1) Grammars | |
| |
| |
| Exercises | |
| |
| |
| Bibliographic | |
| |
| |
| Notes | |