Theory of Computation
R. Inkulu at cse.iitg in Spring 2012


Overview      [Sip]: 1-3

Introduction The Church-Turing Thesis The Chomsky Hierarchy More on Undecidability Intro to Complexity Classes Polynomial Time Polynomial Space
* [HU]: Introduction to Automata Theory, Languages, and Computation by John E Hopcroft and Jeffrey D. Ullman, First Edition.
* [Sip]: Introduction to the Theory of Computation by Michael Sipser, First Edition.