CS21004 Formal Languages and Automata Theory: Spring 2013

CS21004 Formal Languages and Automata Theory

Spring 2013, L-T-P: 3-1-0

General Information

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)

Tentative Coverage

Introduction     Strings and Languages.     [1 hour]

Finite Automata     DFA, NFA, regular expressions, pumping lemma, state minimization.     [10 hours]

Context-free Languages     CFG, Chomsky and Greibach normal forms, pumping lemma, PDA, DPDA, parsing.     [10 hours]

Turing Machines     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.

[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.
[7]     Course page: Formal Languages and Automata Theory, IIT KGP, 2012.

Tests

Class Test 1: 13-Feb-2013 [Questions with solutions]
Mid-Semester Test: 22-Feb-2013 [Questions with solutions]
Class Test 2: 11-Apr-2013 [Questions with solutions]
End-Semester Test: 19-Apr-2013 [Questions with solutions]

Home

Introduction	Strings and Languages.	[1 hour]
Finite Automata	DFA, NFA, regular expressions, pumping lemma, state minimization.	[10 hours]
Context-free Languages	CFG, Chomsky and Greibach normal forms, pumping lemma, PDA, DPDA, parsing.	[10 hours]
Turing Machines	TM, recursive and RE languages, equivalent models, UTM, undecidable problems, reduction, Rice's theorem.	[12 hours]

[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.
[7]	Course page: Formal Languages and Automata Theory, IIT KGP, 2012.