Abstract Machines and Grammars

Contents ......Page 10
Preface ......Page 8
Procedures and Algorithms ......Page 14
Sets, Relations, and Functions ......Page 15
Alphabets and Languages ......Page 17
Summary of Notation ......Page 18
Exercises ......Page 19
2 Context-Free Grammars ......Page 21
Definitions and Examples ......Page 22
Parse Trees and Ambiguity ......Page 24
Leftmost Derivations ......Page 28
Chomsky Normal Form ......Page 29
The Pumping Lemma ......Page 36
Exercises ......Page 41
3 Finite-State Acceptors ......Page 43
Conceptual Description ......Page 44
Nondeterministic Machines ......Page 46
Formal Definitions and Basic Results ......Page 49
Equivalence of Deterministic and Nondeterministic Acceptors ......Page 58
The Pumping Lemma and Languages Which Are Not Finite-State ......Page 61
*Regular Expressions ......Page 64
*Two-Way Finite-State Acceptors ......Page 68
Exercises ......Page 73
4 Finite-State Transducers ......Page 77
Definitions and Examples ......Page 78
*The Pumping Lemma for Finite-State Transducers ......Page 81
*The Multiplication Function ......Page 83
Exercises ......Page 86
The Turing Machine Model ......Page 88
TLΔ, A Programming Language for Turing Machines ......Page 94
TLΔ Abbreviations ......Page 99
TLΔS, TLΔ with Subprocedures ......Page 101
A Compiler for TLΔS ......Page 108
PSΔ, a High-Level Language for Procedures to Compute Functions ......Page 120
A Compiler for PSΔ ......Page 127
The Church/Turing Thesis ......Page 134
Exercises ......Page 136
6 Universal Turing Machines and the Halting Problem ......Page 138
A Universal Turing Machine ......Page 139
The Halting Problem ......Page 141
Exercises ......Page 151
Recursively Enumerable Languages ......Page 153
Recognizable Languages (Recursive Languages) ......Page 157
Exercises ......Page 161
8 *Nondeterministic Turing Machines ......Page 163
An Informal Example ......Page 164
Definitions and Examples ......Page 166
Equivalence of Nondeterministic and Deterministic Turing Machines ......Page 168
Exercises ......Page 169
9 Pushdown Automata ......Page 171
Definitions and Examples ......Page 173
Equivalence of PDA\'s and Context-Free Grammars ......Page 177
*Pushdown Transducers ......Page 186
Deterministic PDA\'s ......Page 187
Exercises ......Page 193
The Post Correspondence Problem ......Page 195
Containment Questions ......Page 202
Ambiguity ......Page 205
Inherent Ambiguity ......Page 206
Exercises ......Page 216
Appendix: The Greek Alphabet ......Page 218
References for Further Reading ......Page 219
Index of Notation ......Page 221
Alphabetic Index ......Page 224