COL 352: Introduction to Automata and Theory of Computation

Semester II 2015-2016

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 2-3, GCL lab   Fri 2-3 , GCL lab   & Tue 2-3, SIT Mtech lab, Thurs 4-5 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)

Background Material in Discrete Structures

Lecture outlines (from past editions of a related course)

Tutorial Problems

Problem Set 0

Problem Set 1
Submit problems 1c, 1d, 2b, 3a by Feb 1, Monday

Minor 1 with solutions

Problem Set 2

Problem Set 3

Minor 2 with solutions

Problem Set 4

Majors with soln and grading guidelines

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 (Many-one 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 non-determinism, 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, Cook-Levin 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