Formal Languages and Automata Theory - CS21004
Spring Semester - 2014
Course Timings
Lectures
Wednesday - 11:30 -12:25 (NR223)
Thursday - 10:30 - 11:25 (NR223)
Friday - 8:30 - 9:25 (NR223)
Tutorial: Friday - 9:30 -10:25 (NR223)
Office Hours: Friday - 15:00 - 17:00 (CS 308)
Teaching Assistants
Manjira Sinha, Sabyasachi Karati, Sumana Gosh, Rajib Lochan Jana
Reference Books
1. Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia.
2. Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.
3. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman,
Introduction to Automata Theory, Languages, and Computation,
Pearson Education Asia.
4. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.
Topics Covered
| January 3rd, 2014 |
Introduction: Alphabet, String and Language |
| January 8th, 2014 |
Deterministic Finite Automata |
| January 9th, 2014 |
Regular Languages, Nondeterministic Finite Automata |
| January 10th, 2014 |
Equivalence of DFA and NFA, Subset Construction |
| January 15th, 2014 |
Regular Expressions |
| January 16th, 2014 |
Equivalence of Regular Expressions and NFA |
| January 17th, 2014 |
Pumping Lemma |
| January 22nd, 2014 |
DFA State minimization |
| January 23rd, 2014 |
DFA State minimization contd ... |
| January 29th, 2014 |
Grammars |
| January 30th, 2014 |
Context Free Grammars (CFL) |
| January 31st, 2014 |
Chomsky Normal Form (CNF) |
| February 5th, 2014 |
Pumping Lemma for Context Free Grammars |
| February 6th, 2014 |
Pushdown Automata (PDA) |
| February 7th, 2014 |
PDA: Formal notation, configuration and acceptance conditions |
| February 12th, 2014 |
Graphical notation for PDA, equivalence of PDA and CFG |
| February 13th, 2014 |
Parsing |
| February 14th, 2014 |
CKY Algorithm, Closure Properties for CFLs |
| February 26th, 2014 |
Acceptance by final state and empty stack |
| February 27th, 2014 |
Acceptance by final state and empty stack contd ... |
| February 28th, 2014 |
Equivalence of PDA and CFG: General Proof |
| March 5th, 2014 |
Equivalence of PDA and CFG: Proof contd ... |
| March 6th, 2014 |
Turing Machines - Definitions |
| March 7th, 2014 |
Turing Machines - construction |
| March 12th, 2014 |
Turing Machines - construction contd ... |
| March 13th, 2014 |
Variants of Turing Machines |
| March 14th, 2014 |
Nondeterministic Turing Machines, Enumerators |
| March 19th, 2014 |
Unrestricted Grammars |
| March 20th, 2014 |
Unrestricted Grammars: Equivalence with Recursively Enumerable Languages |
| March 21st, 2014 |
Counter Automaton |
| March 26th, 2014 |
Closure Properties of Unrestricted Languages |
| March 27th, 2014 |
Universal Turing Machine (UTM) |
| March 28th, 2014 |
Halting Problem (HP) |
| April 2nd, 2014 |
Decidability |
| April 3rd, 2014 |
Decidability contd ... |
| April 4th, 2014 |
Reduction |
| April 9th, 2014 |
Reduction contd ... |
| April 10th, 2014 |
Rice's Theorem |
| April 11th, 2014 |
Undecidable Problems related to CFGs |
Announcements
End Semester Exam
FLAT End Sem Exam will be on April 25th, 2:00 - 5:00 PM.
Second class test
Date:April 15th, 2014. 6:00 - 7:00 PM
Venue: CS 107, CS 108, CS 120.
Seating Arrangement: As per the Student list below
| SI No. 01-25 | 10CS10010 - 12CS10018 | CS 108 |
| SI No. 26-71 | 12CS10019 - 12CS30002 | CS 107 |
| SI No. 72-113 | 12CS30003 - 12CS30044 | CS 120 |
FLAT Mid Sem Exam will be on February 21st, 2:00 - 4:00 PM.
First class test
Date:February 6th, 2014. 6:30 - 7:30 PM
Venue: CS 107, CS 119, CS 120.
Seating Arrangement: As per the Student list below
| SI No. 01-32 | 10CS10010 - 12CS10025 | CS 107 |
| SI No. 33-72 | 12CS10026 - 12CS30003 | CS 119 |
| SI No. 73-112 | 12CS30004 - 12CS30044 | CS 120 |
Please verify that your name appears in this list. Student List
No classes on January 24th.
|