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.

Contact us

School of Mathematical Sciences

NISERPO- Bhimpur-PadanpurVia- Jatni, District- Khurda, Odisha, India, PIN- 752050

Tel: +91-674-249-4081

Corporate Site - This is a contributing Drupal Theme
Design by WeebPal.