Michael Sipser's Introduction to the Theory of Computation. Teaches you formal languages, decidability and complexity theory in a very rigorous way with little prerequisites.