| |
| |
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 | |