Preface

Introduction

Chapter 1: Mathematical Tools and Techniques

Chapter 2: Finite Automata and the Languages They Accept

Chapter 3: Regular Expressions, Nondeterminism, and Kleene's Theorem

Chapter 4: Context-Free Languages

Chapter 5: Pushdown Automata

Chapter 6: Context-Free and Non-Context-Free Languages

Chapter 7: Turing Machines

Chapter 8: Recursively Enumerable Languages

Chapter 9: Undecidable Problems

Chapter 10: Computable Functions

Chapter 11: Introduction to Computational Complexity

Solutions to Selected Exercises

Selected Bibliography

Index of Notation

Index