Formal Languages and Automata Theory  CS21004
Spring Semester  2015
Course Timings
Lectures
Monday  16:30  17:30 (NR323)
Thursday  16:30  17:30 (NR323)
Friday  16:30  17:30 (NR323)
Tutorial: Tuesday  16:30  17:30 (CSE119 and CSE120)
Office Hours: Friday  17:30  19:00 (CS 308)
Teaching Assistants
Mayank Singh, Sudakshina Dutta, Komal Agarwal, Rohan Jain
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 5th, 2015 
Introduction 
January 8th, 2015 
Alphabets, Strings, Languages 
January 9th, 2015 
Problems, Deterministic Finite Automata 
January 12th, 2015 
DFA examples, acceptance condition 
January 15th, 2015 
Regular languages, Closure properties of Regular languages 
January 16th, 2015 
Nondeterministic Finite Automata (NFA) 
January 19th, 2015 
Equivalence of DFA and NFA, epsilonNFA 
January 22nd, 2015 
Regular expressions 
January 23rd, 2015 
Equivalence of regular expressions and NFA, Pumping lemma (basic
idea) 
January 29th, 2015 
Pumping Lemma, Game with the Demon 
January 30th, 2015 
Closure properties to prove nonregularity, DFA state minimization 
February 5th, 2015 
DFA state minimization: algorithm and examples 
February 6th, 2015 
CFGs: Formal notation 
February 9th, 2015 
CFG examples 
February 12th, 2015 
Chomsky Normal Forms (CNF) 
February 13th, 2015 
Parse tree, example proof for a CFG generating balanced parenthesis 
February 26th, 2015 
Pumping lemma for CFLs 
February 27th, 2015 
Closure properties of CFLs 
March 2nd, 2015 
CKY Algorithm 
March 5th, 2015 
Pushdown Automata (PDA) 
March 9th, 2015 
Pushdown Automata  Examples 
March 12th, 2015 
Equivalence of CFGs and PDAs 
March 13th, 2015 
Equivalence of PDAs: empty stack and final state 
March 16th, 2015 
Turing Machines 
March 19th, 2015 
Turing Machines: Examples 
March 20th, 2015 
Turing Machines: Examples 
March 23rd, 2015 
Turing Machines: Variants 
March 26th, 2015 
Enumerator, counter automaton, Unrestricted Grammars 
March 27th, 2015 
Closure properties of r.e. and recursive sets 
March 30th, 2015 
Universal Turing Machine 
April 6th, 2015 
Halting Problem, Decidability 
April 9th, 2015 
Decidability problems for TM 
April 10th, 2015 
Proving Undecidability, Reduction 
April 13th, 2015 
Reduction Theorems and Examples 
April 16th, 2015 
Revision 
Announcements
Tutorial on April 7th has been shifted to 6:007:00 PM instead of
4:305:30 PM
Class Test2 will be on Monday, April 6th, 6:45  7:45 PM
(CSE 107, CSE 119 and CSE 120). The seating arrangment is same as below.
First Class Test will be on Thursday, February 5th, 7:45  8:45 PM
(CSE 107, CSE 119 and CSE 120).
Seating Arrangement:
09CS10044  13CS10043  CS 107 
13CS10044  12CS30013  CS 119 
13CS30015  13IE10032  CS 120 
First FLAT tutorial will be on January 13th, 4:30  5:30 PM (CSE119
for Odd roll numbers and CSE120 for Even Roll numbers)
