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

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.