Formal Languages and Automata Theory - CS21004
Spring Semester - 2016
Course Timings
Lectures
Wednesday - 10:00 - 11:00 (NR223)
Thursday - 09:00 - 10:00 (NR223)
Friday - 11:00 - 12:00 (NR223)
Tutorial: Friday - 12:00 - 13:00 (CSE-119 and CSE-120)
Office Hours: Friday - 18:15 - 19:15 (CSE-308)
Teaching Assistants
Mayank Bhasin, Sandipan Sikdar, Sruthi M and Anurag Verma
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 6th, 2016 |
Introduction |
| January 7th, 2016 |
Alphabets, Strings, Languages |
| January 8th, 2016 |
Problems, Deterministic Finite Automata |
| January 13th, 2016 |
Closure Properties of Regular Languages |
| January 14th, 2016 |
NFA |
| January 15th, 2016 |
Equivalence of NFA and DFA |
| January 20th, 2016 |
Epsilon-NFA, Proving closure properties using NFA |
| January 21st, 2016 |
Regular expressions, regular expressions to NFA conversion |
| January 27th, 2016 |
NFA to regular expression conversion, Proving non-regularity |
| January 28th, 2016 |
Pumping Lemma |
| January 29th, 2016 |
Closure Properties to prove non-regularity, DFA state minimization |
| February 3rd, 2016 |
DFA state minimization |
| February 4th, 2016 |
DFA state minimization, Context Free Languages |
| February 5th, 2016 |
Context Free Grammars |
| February 10th, 2016 |
Proving that a CFG generates a given CFL |
| February 11th, 2016 |
Chomsky Normal Forms (CNF) |
| February 26th, 2016 |
Parse Trees, Pumping Lemma for CFLs |
| March 2nd, 2016 |
CFLs - Closure Properties |
| March 3rd, 2016 |
CKY algorithm, PDA |
| March 4th, 2016 |
PDAs - formal definition and construction |
| March 9th, 2016 |
CFLs - Closure Proterties, Equivaluence of CFG and PDA |
| March 10th, 2016 |
Equivaluence of PDA by emptry stack and final state |
| March 11th, 2016 |
Converting PDAs to CFG |
| March 16th, 2016 |
Converting PDAs to CFG: Proofs |
| March 11th, 2016 |
Turing Machines: Definition, example |
| March 18th, 2016 |
Turing Machines: Examples |
| March 30th, 2016 |
Turing Machines: Examples |
| March 31st, 2016 |
Turing Machines: Variants |
| April 1st, 2016 |
Enumeration Machines, Unrestricted Grammars, Closure Properties
of Recursive Sets |
| April 6th, 2016 |
Universal Turing Machines |
| April 7th, 2016 |
Halting Problem, Membership Problem |
| April 8th, 2016 |
Decidability Problems, Proving Undecidability using Reduction
from HP |
Announcements
Second class test will be held on April 11th, 2016 from 6:00 - 7:00
PM in CSE 107, CSE 119 and CSE 120. Seating arrangement will be the
same as for the first class test.
Tutorial 5 will be held on March 1st, 2016 in CSE-119 (odd roll
numbers) and CSE-120 (even roll numbers) from 5-6 PM.
First class test will be held on February 8th, 2016 from 7:00 - 8:00
PM in CSE 107, CSE 119 and CSE 120.
Seating Arrangement:
| 11CS10053 - 14CS10045 | CS 107 |
| 14CS10046 - 14CS30014 | CS 119 |
| 14CS30015 - 14CS30044 | CS 120 |
First FLAT class will be on January 6th, 10:00 - 11:00 AM (NR223)
Tutorials
Exams
|