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 (CSE-119 and CSE-120)

Office Hours: Friday - 17:30 - 19:00 (CS 308)

Teaching Assistants

Mayank Singh, Sudakshina Dutta, Komal Agarwal, Rohan Jain

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 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, epsilon-NFA
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 non-regularity, 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:00-7:00 PM instead of 4:30-5:30 PM

Class Test-2 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 (CSE-119 for Odd roll numbers and CSE-120 for Even Roll numbers)