Table of Contents
Introduction.
I. FOUNDATIONS.
1. Mathematical Preliminaries.
Set Theory.Cartesian Product, Relations, and Functions.Equivalence
Relations.Countable and Uncountable Sets.Recursive
Definitions.Mathematical Induction.Directed
Graphs.Exercises.Bibliographic Notes.
2. Languages.
Strings and Languages.Finite Specification of Languages.Regular
Sets and Expressions.Exercises.Bibliographic Notes.
II. CONTEXT-FREE GRAMMARS AND PARSING.
3. 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.
4. 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.
5. 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.
III. AUTOMATA AND LANGUAGES.
6. 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.
7. 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.
8.
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.
9. 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.
10. The Chomsky Hierarchy.
Unrestricted Grammars.Context-Sensitive Grammars.Linear-Bounded
Automata.The Chomsky Hierarchy.Exercises.Bibliographic Notes.
IV. DECIDABILITY AND COMPUTABLITY.
11. 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.
12. Numeric Computation.
Computation of Functions.Sequential Operation of Turing
Machines.Composition of Functions.Toward a Programming
Languages.Exercises.Bibliographic Notes.
13. 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.
14. 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.
15. 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.
VI. DETERMINISTIC PARSING.
16. 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.
17.
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. 0201821362T04062001
About the Author
About Thomas Sudkamp
Thomas A. Sudkamp holds a Ph.D. in mathematics from the
University of Notre Dame and worked extensively in industry and for
the Air Force before joining the faculty at Wright State University
where he has taught for over 10 years.
0201821362AB04062001
