Introduction to Automata, Languages and Computation
ABOUT THE COURSE:
Automata, Languages and Computation have been an important part of the curriculum in computer science department for several decades.The automata theory is the study of abstract machines and theirapplication in solving computational problems. Automata is a major part of this course, and is explained elaborately throughout in easily comprehensible ways. Besides providing students with a detailedintroduction to the theories related to computer science, this course also fully covers mathematical preliminaries which are essential to computation.
INTENDED AUDIENCE: Engineering
CORE/ELECTIVE: Core
UG/PG: Both
PREREQUISITES: NIL
INDUSTRY SUPPORT: Software
11221 students have enrolled already!!
ABOUT THE INSTRUCTOR:
Dr. Sourav Mukhopadhyay is an associate professor at Indian Institute of Technology Kharagpur. He has completed his B.Sc (Honours in Mathematics) in 1997 from University of Calcutta, India. He has done M.Stat (in statistics) and M.Tech (in computer science) from Indian Statistical Institute, India, in 1999 and 2001 respectively. He worked with Cryptology Research Group at Indian Statistical Institute as a PhD student and received his Ph.D. degree in Computer Science from there in 2007. He was a Research Assistant at the Computer Science department of School of Computing, National University of Singapore (NUS). He visited InriaRocquencourt, project CODES, France and worked as a post-doctoral research fellows at the School of Computer Engineering, Nanyang Technological University (NTU), Singapore. He was a post-doctoral research fellows and a part time Lecturer with School of Electronic Engineering, Dublin City University (DCU), Ireland.
COURSE LAYOUT:
Week 1 : Finite automata and regular languages Week 2 : Regular expressions Week 3 : Equivalence of DFA and NFA Week 4 : Minimization of finite automata Week 5 : Pumping lemma and its application Week 6 : Context-free grammars and context-free languages Week 7 : Chomsky normal form, closure properties Week 8 : Push down automata Week 9 : Computability Week 10 : Turing machines and variants Week 11 : Time complexity of Turing machines Week 12 : P and NP, NP- completeness
SUGGESTED READING MATERIALS:
N. J. Cutland: Computability: An Introduction to Recursive Function Theory, Cambridge University Press, London,1980.2. M. D. Davis, R. Sigal and E. J. Weyuker: Complexity, Computability and Languages, Academic Press, New York,1994.3. J. E. Hopcroft and J. D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley,California, 1979.4. J. E. Hopcroft, J. D. Ullman and R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, California, 2001.5. H. R. Lewis and C. H. Papadimitriou: Elements of The Theory of Computation, Prentice Hall, Englewood Cliffs, 1981.6. M. Sipser: Introduction to The Theory of Computation, PWS Pub. Co., New York, 1999.7. M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to The Theory of NPCompleteness, Freeman, New York, 1979.
CERTIFICATION EXAM :
The exam is optional for a fee.
Date and Time of Exams: April 27 2019(Saturday). Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
Registration url: Announcements will be made when the registration form is open for registrations.
The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published.
CERTIFICATION:
Final score will be calculated as : 25% assignment score + 75% final exam score
25% assignment score is calculated as 25% of average of Best 8 out of 12 assignments
E-Certificate will be given to those who register and write the exam and score greater than or equal to 40% final score. Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Kharagpur.It will be e-verifiable at nptel.ac.in/noc.
