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. Shashidhar G Koolagudi

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.