Introduction to Languages and The Theory of Computation. John C. Martin

This book is an introduction to the theory of computation. After a chapter presenting the mathematical tools that will be used, the book examines models of computation and the associated languages, from the most elementary to the most general: finite automata and regular languages; context-free languages and pushdown automata; and Turing machines and recursively enumerable and recursive languages.