NIT Goa syllabus Computer Science Engineering | 1st Sem THEORY OF COMPUTATION
THEORY OF COMPUTATION
Formal Languages and Automata Theory: Generative grammar, Chomsky hierarchy, Finite state
Automata: Definition, Concept of Non-determinism, Equivalence of deterministic and Nondeterministic 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-grammars.
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.
J.E.Hopcroft and J.D.Ullman, Introduction to automata, Languages and computation,
H.E.Lewis and C.H. Papadimitiou,Elements of the Theory of Computation,Prentice-Hall of India,
Derickwood, Theory of Computation, John Wiley & Sons.NATIONAL INSTITUTE OF TECHNOLOGY, GOA