Theory of Computation

Course Name: 

Theory of Computation (CS200)


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, regular languages; 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; P,NP,NP-Hard & NP-Complete problems


J.E.Hopcroft and J.D.Ullman, Introduction to automata, Languages and computation, Addison Wesley. 1969
L. Sipser, Theory of Computation, Cengage, 2013.
H.E.Lewis and C.H.Papadimitiou, Elements of the Theory of Computation, Prentice-Hall of
India,1981.Derickwood,Theory of Computation, John Wiley & Sons, 1987.


Computer Science and Engineering

Contact us

Dr. Manu Basavaraju
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.