mca Syllabus

Theory of Computation
Code: PGCS105B
Weekly Contact Hour: 3L
Credit: 3

Course Contents
Finite automata, regular expressions, push-down automata, context free grammars, pumping lemmas. Turing machines (deterministic, non deterministic, multitape) Church-Turing Thesis Decidability and undecidability, diagonalization, and reducibility Halting problem, Post correspondence problem, Rice's Theorem, and other undecidability results Time and space complexity P vs. NP, NP-completeness, Cook's Theorem, and other NP-complete problems PSPACE, PSPACE-completeness, PSPACE-complete problems L vs. NL, NL-completeness, Savitch's Theorem, Immerman-Szelepcsenyi Theorem.

Books
1. Michael Sisper, Introduction to the Theory of Computation, 2nd edition, International Thompson Publishing, 2006.
2. Introduction to Languages and Theory of Computation, Third edition, John C. Martin – McGraw Hill
3. Introduction to Automata Theory, Languages and Computation by J. E. Hopcroft and J. D. Ullman -- pub. PEARSON Education