Abstract Machines and Grammars

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0007.djvu
Preface......Page __sk_0005.djvu
Procedures and Algorithms......Page __sk_0011.djvu
Sets, Relations, and Functions......Page __sk_0012.djvu
Alphabets and Languages......Page __sk_0014.djvu
Summary of Notation......Page __sk_0015.djvu
Exercises......Page __sk_0016.djvu
2 Context-Free Grammars......Page __sk_0018.djvu
Definitions and Examples......Page __sk_0019.djvu
Parse Trees and Ambiguity......Page __sk_0021.djvu
Leftmost Derivations......Page __sk_0025.djvu
Chomsky Normal Form......Page __sk_0026.djvu
The Pumping Lemma......Page __sk_0033.djvu
Exercises......Page __sk_0038.djvu
3 Finite-State Acceptors......Page __sk_0040.djvu
Conceptual Description......Page __sk_0041.djvu
Nondeterministic Machines......Page __sk_0043.djvu
Formal Definitions and Basic Results......Page __sk_0046.djvu
Equivalence of Deterministic and Nondeterministic Acceptors......Page __sk_0055.djvu
The Pumping Lemma and Languages Which Are Not Finite-State......Page __sk_0058.djvu
*Regular Expressions......Page __sk_0061.djvu
*Two-Way Finite-State Acceptors......Page __sk_0065.djvu
Exercises......Page __sk_0070.djvu
4 Finite-State Transducers......Page __sk_0074.djvu
Definitions and Examples......Page __sk_0075.djvu
*The Pumping Lemma for Finite-State Transducers......Page __sk_0078.djvu
*The Multiplication Function......Page __sk_0080.djvu
Exercises......Page __sk_0083.djvu
The Turing Machine Model......Page __sk_0085.djvu
TLΔ, A Programming Language for Turing Machines......Page __sk_0091.djvu
TLΔ Abbreviations......Page __sk_0096.djvu
TLΔS, TLΔ with Subprocedures......Page __sk_0098.djvu
A Compiler for TLΔS......Page __sk_0105.djvu
PSΔ, a High-Level Language for Procedures to Compute Functions......Page __sk_0117.djvu
A Compiler for PSΔ......Page __sk_0124.djvu
The Church/Turing Thesis......Page __sk_0131.djvu
Exercises......Page __sk_0133.djvu
6 Universal Turing Machines and the Halting Problem......Page __sk_0135.djvu
A Universal Turing Machine......Page __sk_0136.djvu
The Halting Problem......Page __sk_0138.djvu
Exercises......Page __sk_0148.djvu
Recursively Enumerable Languages......Page __sk_0150.djvu
Recognizable Languages (Recursive Languages)......Page __sk_0154.djvu
Exercises......Page __sk_0158.djvu
8 *Nondeterministic Turing Machines......Page __sk_0160.djvu
An Informal Example......Page __sk_0161.djvu
Definitions and Examples......Page __sk_0163.djvu
Equivalence of Nondeterministic and Deterministic Turing Machines......Page __sk_0165.djvu
Exercises......Page __sk_0166.djvu
9 Pushdown Automata......Page __sk_0168.djvu
Definitions and Examples......Page __sk_0170.djvu
Equivalence of PDA\'s and Context-Free Grammars......Page __sk_0174.djvu
*Pushdown Transducers......Page __sk_0183.djvu
Deterministic PDA\'s......Page __sk_0184.djvu
Exercises......Page __sk_0190.djvu
The Post Correspondence Problem......Page __sk_0192.djvu
Containment Questions......Page __sk_0199.djvu
Ambiguity......Page __sk_0202.djvu
Inherent Ambiguity......Page __sk_0203.djvu
Exercises......Page __sk_0213.djvu
Appendix: The Greek Alphabet......Page __sk_0215.djvu
References for Further Reading......Page __sk_0216.djvu
Index of Notation......Page __sk_0218.djvu
Alphabetic Index......Page __sk_0221.djvu