Formal Languages and Automata Theory  CS21004
Spring Semester  2019
Instructors
Prof. Soumyajit Dey will be teaching Section2 (Even Roll Numbers)
and I will be teaching Section1 (Odd Roll Numbers). The Timings below
are same for both the sections, except that the classes for Section2
will be in NC 234.
Course Timings
Lectures
Wednesday  08:00  9:55 (NC233)
Thursday  10:00  10:55 (NC233)
Tutorial: Monday  10:00  10:55 (NC233)
Teaching Assistants
Madhumita Mallick, Soumyajit Chatterjee, Bishal Santra and Srinidhi V Bhat
Reference Books
 Dexter C. Kozen, Automata and Computability,
Undergraduate Texts in Computer Science, Springer.
 Harry R. Lewis and Christos H. Papadimitriou, Elements of
the Theory of Computation, Pearson Education Asia.
 Michael Sipser, Introduction to the Theory of
Computation, PWS Publishing.
Topics Covered
January 2nd, 2019 
Introduction 
January 3rd, 2019 
Alphabets, Strings, Languages 
January 9th, 2019 
DFA 
January 10th, 2019 
Regular Languages, Closure PRoperties 
January 16th, 2019 
NFA, epsilonNFA, Equivalence of NFA and DFA 
January 17th, 2019 
Closure Properties using NFA 
January 23rd, 2019 
Regular Expressions, Right Linear Grammas, Equivalence with Finite
Automata 
January 24th, 2019 
Proving Nonregularity using Pumping Lemma 
January 30th, 2019 
Pumping Lemma, DFA state minimization 
Feb 2nd, 2019 
DFA state minimization Algorithm 
Feb 6th, 2019 
Pumping Lemma problems, Myhill Nerode Relations 
Feb 7th, 2019 
Myhill Nerode Theorem, Proving Nonregularity 
Feb 13th, 2019 
Context Free Grammars 
Feb 27th, 2019 
Context Free Grammars  Chomsky Normal Form, Derivation Tree 
March 7th, 2019 
Pumping Lemma for CFLs, Pushdown Automata (PDA) 
March 8th, 2019 
Pushdown Automata Contd ... 
March 13th, 2019 
Equivalence of CFG and PDA 
March 14th, 2019 
Parsing 
March 20th, 2019 
Closure Properties of CFLs, CKY Algorithm 
March 27th, 2019 
CKY Algorithm, DPDA, Unrestricted Grammar 
March 28th, 2019 
Turing Machines 
April 3rd, 2019 
Turing Machines (TMs), Variants of TMs 
April 4th, 2019 
Decidability 
April 10th, 2019 
Halting Problem, Undecidability 
April 11th, 2019 
Reduction to prove undecidability 
Tutorials
January 7th, 2019 
Problems 
Solutions 
January 14th, 2019 
Problems 
Solutions 
January 21st, 2019 
Problems 
Solutions 
January 28th, 2019 
Problems 
Solutions 
Feb 4th, 2019 
Problems 
Solutions 
Feb 14th, 2019 
Problems 
Solutions 
March 11th, 2019 
Problems 
Solutions 
March 18th, 2019 
Problems 
Solutions 
March 25th, 2019 
Problems 
Solutions 
April 1st, 2019 
Problems 
Solutions 
April 8th, 2019 
Problems 
Solutions 
April 15th, 2019 
Problems 
Solutions 
Announcements
Class Test 1 will be held on January 29th, 6:30  7:30 PM. Class
Rooms: CSE 107, 302, 119, 120. (Seating Arrangement)
First class will be held on January 2nd, 2019 from 9:00  9:55
AM in NC 233.
