NIT Goa syllabus Computer Science Engineering I Sem Theory of Computation

 

 

 

 

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,

Narossa/Addison Wesley.

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.NATIONAL INSTITUTE OF TECHNOLOGY, GOA

Leave a Comment