Theory of Computation
Course Name:
Theory of Computation (CS200)
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, 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
References:
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.
Department:
Computer Science and Engineering