Introduction to Automata and Formal Languages

Just the usual stuff: finite automata and regular languages; context-free grammars and their languages; pushdown automata; Turing machines, string rewriting systems, RE languages and a couple of undecidability results.

Literature

Introdution to the Theory of Computation by Sipser

The Language of Machines by Floyd and Beigel

Introduction to Automata Theory, Languages, and Computation by Hopcroft, Ullman, Motwani