CS208: Automata Theory and Logic
(Spring 2013)


Teaching Staff

Instructor Supratik Chakraborty
Friendly TAs Khushraj Madnani Saptarshi Sarkar Karan Chawla Deepak Agrawal Naman Jain


What When Where
Mon 9:30 Tue 10:30
Thurs 11:30
Classroom LCC 02, Lecture Hall Complex
Office hour
Thurs 17:00-18:00
(by email appointment)
CFDVS Lab 1 (Maths basement)


Midterm 30%
Endterm 50%
Classworks and quizes 20%

Ground Rules

Reading Material

Homeworks, Classworks, Practice Questions and Exams

Problems from current offering of course

In-class Quiz 1 Thu, Jan 10
In-class Quiz 2 Mon, Jan 21
In-class Quiz 3 Mon, Feb 4
Mid-term exam Tue, Feb 19

Selected problems from earlier offerings of course

Problem set 1 Problem set 2 Problem set 3 Problem set 4
Problem Set 5 Problem Set 6 Problem Set 7 Problem Set 8
Problem Set 9 Problem Set 10 Problem Set 11 Problem Set 12
Problem Set 13 Problem Set 14 Problem Set 15 Problem Set 16
Problem Set 17 Problem Set 18 Problem Set 19 Problem Set 20
Problem Set 21 Problem Set 22 Problem Set 23 Problem Set 24

Lecture Schedule

DateTopicsReading assignment from textbook
Jan 7 Introduction, course logistics, examples of problems that cannot be solved by computers, a simple proof of unsolvability Chapter 1
Jan 8 Formalizing computation as acceptance/rejection of finite strings, uncountable problems to solve vs countable programs to solve them Chapter 1
Jan 10 Notion of a finite state automaton, illustration of finite state automata accepting simple-to-describe languages, in-class quiz1 Sections 2.1, 2.2, 2.3
Jan 14 Solutions to quiz1, deterministic and non-deterministic finite state automata and their equivalence Sections 2.2, 2.3, 2,5
Jan 15 Non-deterministic finite state automata: succinctness and intuitive appeal, Boolean closure of languages accepted by finite state automata Sections 2.2, 2.3, 2.5
Jan 17 NFAs with epsilon transitions, and their equivalence with NFAs without epsilon transitions, succinctness issues, closure of languages accepted by NFA under concatenation and Kleene start Sections 2.5, 3.1, 3.2, 3.3
Jan 21 In-class quiz 2
Jan 22 Regular expressions and their relation to NFA (guest lecture by Prof. Ashutosh Trivedi) Sections 3.1, 3.2, 3.3
Slides by Prof. Trivedi
Jan 24 Properties of regular expressions as an algebraic structure (guest lecture by Prof. Ashutosh Trivedi) Sections 3.3, 3.4
Jan 28 Discussion on solutions of in-class quiz2, proving identities involving regular expressions Sections 3.4, 4.1, 4.2
Jan 31
(2 lectures)
Using product construction to prove languages regular, Pumping Lemma for regular languages and some applications Sections 4.1, 4.2, 4.3
Feb 4 In-class quiz 3, guest lecture by Prof. Ashutosh Trivedi: introduction to logic (for expressing regular languages) Notes by Prof.Narayan Kumar (CMI)
Feb 5 Solutions to quiz 3, More about logic and its connections to automata theory Same as above
Feb 7 Monadic second order logic (MSO), encoding words accepted by an automaton using MSO Same as above. For those interested further, see also notes by Prof. Narayan Kumar (CMI) on encoding models of MSO formulae using NFA
Feb 11 Closure of regular languages under substitution, homomorphisms, inverse homomorphisms; examples illustrating applications in proving regularity of languages Sections 4.2, 4.3, 4.4 of textbook
Feb 12 More examples illustrating usage of closure properties in proving regularity/non-regularity of languages, answering questions about emptiness and finiteness of regular languages by black-box testing of automata Sections 4.3, 4.4 of textbook
Feb 14 Minimization of deterministic finite automata, overview of our study of regular languages Sections 4.4, 8.1 and 8.2 of textbook
Feb 18-23 Mid-semester exams
Feb 25 Introduction to Turing Machines (TM): notation and examples, acceptance by final state Sections 8.1 and 8.2
Feb 26 Equivalence of acceptance by final state and acceptance by halting, TM with multi-track tapes and multiple tapes Sections 8.3 and 8.4
Feb 28 More on multi-tape and multi-track TMs, TMs with tape extending to infinity in both directions, equivalence of above TM extensions to basic TM model with a single track, single tape, extending to infinity only in one direction. Non-deterministic TMs and tree of configurations. eq Sections 8.3, 8.4, 8.5
Mar 4 Equivalence of expressive power of non-deterministic Turing machines and deterministic Turing machines. Basics of deterministic and non-deterministic time and space complexity classes. Sections 8.4, 8.5
Mar 5 Notion of algorithms and procedures. Encoding Turing machines and strings as integers, Cantor's diagonalization to show the existence of problems that cannot be solved by a Turing Machine Sections 9.1 and 9.2
Mar 7 Notion of undecidability. Recursive and recursively enumerable languages. Examples of languages that are/are not recursive, and examples of languages that are/are not recursively enumerable. Sections 9.1, 9.2 and 9.3
Mar 11 No class due to Foundation Day
Mar 12 Sections 9.3 and 9.4