CS21004 Formal Languages and Automata Theory |
Spring 2012, 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 V4

Syllabus: Official site

Teaching Assistants: Anupam Sadhukhan, Binanda Sengupta,## 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 pages.

[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.

[5] Course page: Theory of Computation, IITK, 2002. [6] Course page: Formal Languages and Automata Theory, IIT KGP, 2011. ## Tests

Class Test 1

09-February-2012 (Thursday), 07:00pm--08:00pm, F-142 (Raman Auditorium)

Questions with solutionsMid-Semester Test:

17-February-2012 (Friday), 02:00-04:00pm, V1, V2, V3

Questions with solutionsClass Test 2

09-April-2012 (Monday), 08:00pm--09:00pm, F-142 (Raman Auditorium)

Questions with solutionsEnd-Semester Test:

20-April-2012 (Friday), 02:00-05:00pm, V1, V2, V3

Questions with solutions