# Course

## M469 - Theory of Computation

Course No:
M469
Credit:
4
Prerequisites:
M101
Approval:
2014
UG-Elective
PG-Core
Syllabus:
Automata and Language Theory: Finite automata, regular expression, pumping lemma, context free grammar, context free languages, Chomsky normal form, push down automata, pumping lemma for CFL;
Computability: Turing machines, Churh-Turing thesis, decidability, halting problem, reducibility, recursion theorem;
Complexity: Time complexity of Turing machines, Classes P and NP, NP completeness, other time classes, the time hierarchy.
Reference Books:
1. J. E. Hopcroft, R. Motwani, J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, Addison-Wesley, 2006.
2. H. Lewis, C. H. Papadimitriou, “Elements of the Theory of Computation”, Prentice- Hall, 1997.
3. M. Sipser, “Introduction to the Theory of Computation”, PWS Publishing, 1997.