Date  Topics  Reading 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 simpletodescribe languages,
inclass quiz1 
Sections 2.1, 2.2, 2.3 
Jan 14 
Solutions to quiz1, deterministic and nondeterministic finite
state automata and their equivalence 
Sections 2.2, 2.3, 2,5 
Jan 15 
Nondeterministic 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 
Inclass 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 inclass 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 
Inclass 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/nonregularity of languages, answering questions
about emptiness and finiteness of regular languages by blackbox
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 1823  Midsemester 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 multitrack tapes and
multiple tapes 
Sections 8.3 and 8.4 
Feb 28 
More on multitape and multitrack 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. Nondeterministic TMs and tree of configurations.
eq 
Sections 8.3, 8.4, 8.5 
Mar 4 
Equivalence of expressive power of nondeterministic Turing
machines and deterministic Turing machines. Basics of deterministic
and nondeterministic 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 