
COL 352: Introduction to Automata and Theory of Computation
Semester II 20152016
Instructor : Sandeep Sen


Lectures: (Slot H) Mon, Wed 11  11:50 , Thurs : 12  12:50 Venue LH 416
Office hours: W: 12  1
Teaching Assistants:
Office hours/help session
Dhiraj Madan
Sai Praneeth
Akshay Rajput
Aounon Kumar
Wed 23, GCL lab Fri 23 , GCL lab & Tue 23, SIT Mtech lab, Thurs 45 505,
Bharti
Please send an email to the TA to confirm the venue of the meeting.
Grading
The total will be computed as Minors 1 and 2  20% each, Major 40%, Quizes
and Assignments  20%.
Note that students having
less than 75% attendence will be reported for possible penal action according
to the new attendence rules of the institute.
Prerequisites: CSL105 (Discrete Structures or equivalent)
Tutorial Problems
Problem Set 1
Submit problems 1c, 1d, 2b, 3a by Feb 1, Monday
Lectures
Lecture 2 (Language, decision, cardinality)
Lecture 3 (Diagonalization argument, discussion)
Lectures 4,5 (Finite State Automaton)
Lectures 6,7 (NFA)
Lectures 8 (Regular expressions)
Lectures 9,10 (r.e. and FA)
Lectures 11 (DFA to r.e.)
Lectures 12 (Pumping Lemma)
Lectures 13 (PL and closure properties)
Lectures 14 (Discussion)
Lecture 15,16 (Myhill Nerode Theorem)
Lecture 17 (Minimizing DFA )
Lecture 18 (Problem discussions)
Lecture 19 (Context Free Grammar)
Lecture 20 (CYK algorithm)
Lecture 21,22 (PDA)
Lecture 23 (Properties of CFL)
Lecture 24,25 (Turing machines)
Lecture 26,27 (Re languages and generators)
Lecture 28 (RAM model, counter machines)
Lecture 29, 30 (Properties of re, Universal TM )
Lecture 31 (Manyone TM computable reduction )
Lecture 32 (Rice's theorem for recursive index )
Lecture 33 (Undecidable problems on TM)
Lecture 34 (Time and Space Complexity)
Lecture 35 (Relationship between classes)
Lecture 36 (Classes P and NP)
Lecture 37 (Poly time redn and NPC)
Lecture 38 (Cook Levin Theorem)
Recommended : CSL201 (Data Structures)
Contents.
Formal Languages Regular Languages, Finite Automata, equivalence, minimization, Myhill Nerode
theorem, Introduction to nondeterminism, Context Free Grammars, Pushdown
Automata, Equivalence and Applications
Computability : Turing Machines, Recursive and recursively enumerable sets, RAMs and
equivalence, Universal Turing Machine, Undecidability, Rices theorem for
recursive and re sets, Recursive function theory and equivalence, Church
Turing Thesis
Computational Complexity : Space Time complexity, Savage's theorem,
Complexity classes, Complete problems, NP completeness, CookLevin
theorem and reductions
Reference books
Introduction to Automata Theory, Languages and Computation
by Hopcroft and Ullman, Pub: Narosa
Automata and Computability Kozen
Pub Springer (Indian reprint available)
Sandeep Sen
Last modified: Wed Jan 1 2014