Formal Languages and Automata Theory - CS21004

Spring Semester - 2019


Prof. Soumyajit Dey will be teaching Section-2 (Even Roll Numbers) and I will be teaching Section-1 (Odd Roll Numbers). The Timings below are same for both the sections, except that the classes for Section-2 will be in NC 234.

Course Timings


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

  1. Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.
  2. Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia.
  3. 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, epsilon-NFA, 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 Non-regularity 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 Non-regularity
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


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


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.