| CS21004 Formal Languages and Automata Theory | Spring 2011, L-T-P: 3-1-0 |
General Information
Instructor: Abhijit Das, CSE Department
Timing: Slot A (Monday 07:30-09:25, Tuesday 11:30-12:25, Wednesday 10:30-11:25)
Venue: Room No 120, CSE Department
Syllabus: Official site
Teaching Assistants: Anup Kumar Bhattacharya, Binanda Sengupta, Sabyasachi Karati.Tentative Coverage
Introduction Strings and Languages. [1 week] Finite Automata DFA, NFA, regular expressions, pumping lemma, state minimization. [4 weeks] Context-free Languages CFG, Chomsky and Greibach normal forms, pumping lemma, PDA, DPDA, parsing. [4 weeks] Turing Machines TM, recursive and RE languages, equivalent models, UTM, undecidable problems, reduction, Rice's theorem. [4 weeks] Textbook and References
I will mostly follow the first book. The remaining books are good references. Also look at my course page for a similar course in IITK.
[1] Dexter C Kozen, Automata and Computability, Springer, 1997. [2] Harry R Lewis and Christos H Papadimitriou, Elements of the Theory of Computation, second edition, Prentice Hall, 1998. [3] John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, third edition, Prentice Hall, 2007. [4] Michael Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005. Tests
- Class Test 1: Feb 10, 2011 (Thursday), 06:30pm -- 07:30pm, Room No: F-116 (Bhatnagar)
Questions | Solutions- Mid-Semester Test: Feb 18, 2011 (Friday), 02:00pm -- 04:00pm, Room No: V1
Questions | Solutions- Class Test 2: Apr 11, 2011 (Monday), 06:00pm -- 07:00pm, Room No: F-116 (Bhatnagar)
Questions | Solutions- End-Semester Test: Apr 21, 2011 (Thursday), 02:00pm -- 05:00pm, Room No: V1
Questions | Solutions