Theory of Computation

Course Name: 

Theory of Computation (CO201)

Programme: 

B.Tech (CSE)

Semester: 

Third

Category: 

Programme Core (PC)

Credits (L-T-P): 

04 (3-1-0)

Content: 

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.

References: 

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.

Department: 

Computer Science and Engineering
 

Contact us

P Santhi Thilagam
Associate Professor and Head
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.

  • Hot line: +91-0824-2474060

Connect with us

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