Maheshwari A., Smid M. Introduction to Theory of Computation

Ottawa: Carleton University, 2017. - 251 p.This is a free textbook for an undergraduate course on the Theory of Computation, which we have been teaching at Carleton University since 2002. Until the 2011/2012 academic year, this course was offered as a second-year course and was compulsory for all Computer Science students. Starting with the 2012/2013 academic year, the course has been downgraded to a third-year optional course. The course as we teach it today has been influenced by the following two textbooks:
• Introduction to the Theory of Computation (2nd. ed.), by Michael Sipser, Thomson Course Technnology, Boston, 2006.
• Einfuhrung in die Theoretische Informatik, by Klaus Wagner, Springer-Verlag, Berlin, 1994.Finite Automata and Regular Languages.
Context-Free Languages.
Turing Machines and the Church-Turing Thesis.
Decidable and Undecidable Languages.
Complexity Theory.