|CS21004 Formal Languages and Automata Theory
||Spring 2013, L-T-P: 3-1-0
Instructor: Abhijit Das, CSE Department
Timing: Slot E [Wednesday 11:30-12:25, Thursday 10:30-11:25 (Tutorial), Friday 08:30-10:25]
Venue: Room No NR223
Syllabus: Official site
Teaching Assistant: Sabyasachi Karati
List of Students (possibly incomplete)
||Strings and Languages.
|| [1 hour]
||DFA, NFA, regular expressions, pumping lemma, state minimization.
|| [10 hours]
||CFG, Chomsky and Greibach normal forms, pumping lemma, PDA, DPDA, parsing.
|| [10 hours]
||TM, recursive and RE languages, equivalent models, UTM, undecidable problems, reduction, Rice's theorem.
|| [12 hours]
Textbook and References
I will mostly follow the first book. The remaining books are good references.
Also look at my course pages.
||Dexter C Kozen,
Automata and Computability, Springer, 1997.|
||Harry R Lewis and Christos H Papadimitriou,
Elements of the Theory of Computation, second edition, Prentice Hall, 1998.|
||John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman,
Introduction to Automata Theory, Languages, and Computation, third edition,
Prentice Hall, 2007.|
Introduction to the Theory of Computation,
second edition, Course Technology, 2005.|
||Course page: Theory of Computation, IITK, 2002.
||Course page: Formal Languages and Automata Theory, IIT KGP, 2011.
||Course page: Formal Languages and Automata Theory, IIT KGP, 2012.