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

IntroductionStrings and Languages. [1 week] Finite AutomataDFA, NFA, regular expressions, pumping lemma, state minimization. [4 weeks] Context-free LanguagesCFG, Chomsky and Greibach normal forms, pumping lemma, PDA, DPDA, parsing. [4 weeks] Turing MachinesTM, 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 | SolutionsMid-Semester Test:Feb 18, 2011 (Friday), 02:00pm -- 04:00pm, Room No: V1

Questions | SolutionsClass Test 2:Apr 11, 2011 (Monday), 06:00pm -- 07:00pm, Room No: F-116 (Bhatnagar)

Questions | SolutionsEnd-Semester Test:Apr 21, 2011 (Thursday), 02:00pm -- 05:00pm, Room No: V1

Questions | Solutions