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.