Models of Computation and Formal Languages
Rob Taylor · 1997
Preface Chapter 0 - Mathematical Preliminaries Part I: Models of Computation Chapter 1 - Turning Machines Chapter 2 - Additional Varieties of Turning Machines Chapter 3 - An Introduction to Recursion Theory Chapter 4 - Markov Algorithms Chapter 5 - Register Machines Chapter 6 - Post Systems (Optional) Chapter 7 - The Vector Machine Model of Parallel Computation (Optional) Chapter 8 - The Bounds of Computability Part II: A Hierarchy of Automata and Formal Languages Chapter 9 - Regular Languages and Finite-State Automata Chapter 10 - Context-Free Languages and Pushdown-Stock Automata Chapter 11 - Context-Free Languages and Compiler Design Theory (Optional) Chapter 12 - Context-Sensitive Languages and Linear Bounded Automata Chapter 13 - Generative Grammars an the Chomsky Hierarchy Epilogue