Course Name: 

Formal Languages & Automata Theory (AI456)


B.Tech (AI)


Programme Specific Electives (PSE)

Credits (L-T-P): 

(3-0-0) 3


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


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.


Information Technology

Contact us

Head of the Department,
Department of Information Technology,
National Institute of Technology Karnataka,
SurathkalP. O. Srinivasnagar, Mangalore - 575 025
Ph.:    +91-824-2474056
Email:  hodit [at] nitk [dot] edu [dot] in

Web Admin: Sowmya Kamath S

Connect with us

We're on Social Networks. Follow us & stay in touch.