Formal Languages and Automata Theory - CS21004
Spring Semester - 2019
Instructors
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
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, 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 |
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.
|