This book presents automata theory, formal languages, and computational complexity as a coherent theory. It includes end-of-chapter questions, bibliographies, and exercises. Problems of highest and intermediate difficulty are marked respectively with double or single stars. .

Preliminaries -- Finite automata and regular expressions -- Properties of regular sets -- Context-free grammars -- Pushdown automata -- Properties of context-free languages -- Turing machines -- Undecidability -- The Chomsky hierarchy -- Deterministic context-free languages -- Closure properties of families of languages -- Computational complexity theory -- Intractable problems -- Highlights of other important language classes.