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

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

Home