Automata and Computability, Dexter Kozen, Springer
Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Addison-Wesley
Theory of Computation, Derick Wood, Wiley
Introduction to Formal Language Theory, M. Harrison, Addison Wesley
The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Martin Davis, Raven Press
Computational Complexity, A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009
Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 2000
Computational Complexity, Christos Papadimitriou, Addison Wesley