Theory of Computation

Course Name: 

Theory of Computation (CO201)


B.Tech (CSE)




Programme Core (PC)

Credits (L-T-P): 

04 (3-1-0)


Formal Languages and Automata Theory: Generative grammar, Chomsky hierarchy, Finite state Automata: Definition, Concept of Non-determinism, Equivalence of deterministic and Non-deterministic Automata, Relation between CFL and Type3 grammars, Pumping Lemma for CFL, Closure properties, Push down Automata: Definition, Equivalence between NPDA and context free grammars, Pumping Lemma for C.F.L's,Decision problems, Closure properties, Turing machines:Definition, extension to turing machines: Multi-track, Multi-tape, and Non determinism, TM as an acceptor, TM as a computing device, Relation between TM and type-0-grammar, Universal Turing Machine, Concept of computability, Undecidable problems, Recursive function theory: Primitive recursive functions, general recursive function, relation between general recursive functions and Turing machines, Church’s thesis, P, NP, NP- Hard & NP- Complete problems.


1. J.E.Hopcroft and J.D.Ullman, "Introduction to Automata, Languages and Computation", Addison Wesley.
2. H. E. Lewis and C. H. Papadimitiou, "Elements of the Theory of Computation", Prentice-Hall of India, 1981.
3. Derickwood, "Theory of Computation", John Wiley and Sons.


Computer Science and Engineering

Contact us

Dr. Alwyn Roshan Pais
Head of the Department
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.

Hot line: +91-0824-2474053
Email: hodcse[AT]nitk[DOT]ac[DOT]in


Connect with us

We're on Social Networks. Follow us & get in touch.