IT474
Course Name:
Formal Languages & Automata Theory (IT474)
Programme:
B.Tech (AI)
Category:
Programme Specific Electives (PSE)
Credits (L-T-P):
(3-0-0) 3
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. Pushdown 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
M. 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:
Information Technology